License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2020.68
URN: urn:nbn:de:0030-drops-122267
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12226/
Go to the corresponding LIPIcs Volume Portal

Wang, Haitao

On the Planar Two-Center Problem and Circular Hulls

pdf-format:
LIPIcs-SoCG-2020-68.pdf (0.6 MB)

Abstract

Given a set S of n points in the Euclidean plane, the two-center problem is to find two congruent disks of smallest radius whose union covers all points of S. Previously, Eppstein [SODA'97] gave a randomized algorithm of O(nlog²n) expected time and Chan [CGTA'99] presented a deterministic algorithm of O(nlog² nlog²log n) time. In this paper, we propose an O(nlog² n) time deterministic algorithm, which improves Chan’s deterministic algorithm and matches the randomized bound of Eppstein. If S is in convex position, we solve the problem in O(nlog nlog log n) deterministic time. Our results rely on new techniques for dynamically maintaining circular hulls under point insertions and deletions, which are of independent interest.

BibTeX - Entry

@InProceedings{wang:LIPIcs:2020:12226,
  author =	{Haitao Wang},
  title =	{{On the Planar Two-Center Problem and Circular Hulls}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{68:1--68:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Sergio Cabello and Danny Z. Chen},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12226},
  URN =		{urn:nbn:de:0030-drops-122267},
  doi =		{10.4230/LIPIcs.SoCG.2020.68},
  annote =	{Keywords: two-center, disk coverage, circular hulls, dynamic data structures}
}

Keywords: two-center, disk coverage, circular hulls, dynamic data structures
Collection: 36th International Symposium on Computational Geometry (SoCG 2020)
Issue Date: 2020
Date of publication: 08.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI