Kyungjin Cho ; Eunjin Oh ; Haitao Wang ; Jie Xue - Optimal Algorithm for the Planar Two-Center Problem

theoretics:13502 - TheoretiCS, November 5, 2024, Volume 3 - https://doi.org/10.46298/theoretics.24.23
Optimal Algorithm for the Planar Two-Center ProblemArticle

Authors: Kyungjin Cho ; Eunjin Oh ; Haitao Wang ; Jie Xue

    We study a fundamental problem in Computational Geometry, the planar two-center problem. In this problem, the input is a set $S$ of $n$ points in the plane and the goal is to find two smallest congruent disks whose union contains all points of $S$. A longstanding open problem has been to obtain an $O(n\log n)$-time algorithm for planar two-center, matching the $\Omega(n\log n)$ lower bound given by Eppstein [SODA'97]. Towards this, researchers have made a lot of efforts over decades. The previous best algorithm, given by Wang [SoCG'20], solves the problem in $O(n\log^2 n)$ time. In this paper, we present an $O(n\log n)$-time (deterministic) algorithm for planar two-center, which completely resolves this open problem.


    Volume: Volume 3
    Published on: November 5, 2024
    Accepted on: October 5, 2024
    Submitted on: May 1, 2024
    Keywords: Computer Science - Computational Geometry

    Consultation statistics

    This page has been seen 127 times.
    This article's PDF has been downloaded 51 times.