Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2007.08784 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915006107353088 |
|---|---|
| author | Cho, Kyungjin Oh, Eunjin Wang, Haitao Xue, Jie |
| author_facet | Cho, Kyungjin Oh, Eunjin Wang, Haitao Xue, Jie |
| contents | 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 $Ω(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2007_08784 |
| institution | arXiv |
| publishDate | 2020 |
| record_format | arxiv |
| spellingShingle | Optimal Algorithm for the Planar Two-Center Problem Cho, Kyungjin Oh, Eunjin Wang, Haitao Xue, Jie Computational Geometry 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 $Ω(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. |
| title | Optimal Algorithm for the Planar Two-Center Problem |
| topic | Computational Geometry |
| url | https://arxiv.org/abs/2007.08784 |