Document Open Access Logo

On the Planar Two-Center Problem and Circular Hulls

Author Haitao Wang

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2020.68.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Haitao Wang
  • Department of Computer Science, Utah State University, Logan, UT 84322, USA

Cite AsGet BibTex

Haitao Wang. On the Planar Two-Center Problem and Circular Hulls. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 68:1-68:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.SoCG.2020.68

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
  • Theory of computation → Computational geometry
Keywords
  • two-center
  • disk coverage
  • circular hulls
  • dynamic data structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. P.K. Agarwal and J.M. Phillips. An efficient algorithm for 2D Euclidean 2-center with outliers. In Proceedings of the 16th Annual European Symposium on Algorithms (ESA), pages 64-75, 2008. Google Scholar
  2. P.K. Agarwal and M. Sharir. Planar geometric location problems. Algorithmica, 11:185-195, 1994. Google Scholar
  3. P.K. Agarwal, M. Sharir, and E. Welzl. The discrete 2-center problem. Discrete and Computational Geometry, 20:287-305, 1998. Google Scholar
  4. E.M. Arkin, J.M. Díaz-Bá~nez, F. Hurtado, P. Kumar, J.S.B. Mitchell, B. Palop, P. Pérez-Lantero, M. Saumell, and R.I. Silveira. Bichromatic 2-center of pairs of points. Computational Geometry: Theory and Applications, 48:94-107, 2015. Google Scholar
  5. M. Blum, R.W. Floyd, V. Pratt, R.L. Rivest, and R.E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7:448-461, 1973. Google Scholar
  6. T.M. Chan. More planar two-center algorithms. Computational Geometry: Theory and Applications, 13:189-198, 1999. Google Scholar
  7. T.M. Chan. A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions. Discrete and Computational Geometry, 56:860-865, 2016. Google Scholar
  8. B. Chazelle. An optimal algorithm for intersecting three-dimensional convex polyhedra. SIAM Journal on Computing, 21(4):671-696, 1992. Google Scholar
  9. B. Chazelle and J. Matoušek. On linear-time deterministic algorithms for optimization problems in fixed dimension. Journal of Algorithms, 21:579-597, 1996. Google Scholar
  10. R. Cole. Slowing down sorting networks to obtain faster sorting algorithms. Journal of the ACM, 34(1):200-208, 1987. Google Scholar
  11. D.P. Dobkin and D.G. Kirkpatrick. Determining the separation of preprocessed polyhedra - A unified approach. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP), pages 400-413, 1990. Google Scholar
  12. J. Driscoll, N. Sarnak, D. Sleator, and R.E. Tarjan. Making data structures persistent. Journal of Computer and System Sciences, 38(1):86-124, 1989. Google Scholar
  13. M.E. Dyer. On a multidimensional search technique and its application to the Euclidean one centre problem. SIAM Journal on Computing, 15(3):725-738, 1986. Google Scholar
  14. H. Edelsbrunner, D. Kirkpatrick, and R. Seidel. On the shape of a set of points in the plane. IEEE Transactions on Information Theory, 29:551-559, 1983. Google Scholar
  15. D. Eppstein. Dynamic three-dimensional linear programming. ORSA Journal on Computing, 4:360-368, 1992. Google Scholar
  16. D. Eppstein. Faster construction of planar two-centers. In Proc. of the 8th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 131-138, 1997. Google Scholar
  17. D. Halperin, M. Sharir, and K. Goldberg. The 2-center problem with obstacles. Journal of Algorithms, 42:109-134, 2002. Google Scholar
  18. J. Hershberger. A faster algorithm for the two-center decision problem. Information Processing Letters, 1:23-29, 1993. Google Scholar
  19. J. Hershberger and S. Suri. Finding tailored partitions. Journal of Algorithms, 3:431-463, 1991. Google Scholar
  20. J. Jaromczyk and M. Kowaluk. An efficient algorithm for the Euclidean two-center problem. In Proceedings of the 10th Annual Symposium on Computational Geometry (SoCG), pages 303-311, 1994. Google Scholar
  21. M. Katz and M. Sharir. An expander-based approach to geometric optimization. SIAM Journal on Computing, 26(5):1384-1408, 1997. Google Scholar
  22. S.K. Kim and C.-S. Shin. Efficient algorithms for two-center problems for a convex polygon. In Proceedings of the 6th International Computing and Combinatorics Conference (COCOON), pages 299-309, 2000. Google Scholar
  23. N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. Journal of the ACM, 30(4):852-865, 1983. Google Scholar
  24. N. Megiddo. Linear-time algorithms for linear programming in R³ and related problems. SIAM Journal on Computing, 12(4):759-776, 1983. Google Scholar
  25. N. Sarnak and R.E. Tarjan. Planar point location using persistent search trees. Communications of the ACM, 29:669-679, 1986. Google Scholar
  26. M. Sharir. A near-linear algorithm for the planar 2-center problem. Discrete and Computational Geometry, 18:125-134, 1997. Google Scholar
  27. X. Tan and B. Jiang. Simple O(nlog²n) algorithms for the planar 2-center problem. In Proceedings of the 23rd International Computing and Combinatorics Conference (COCOON), pages 481-491, 2017. Google Scholar
  28. H. Wang and J. Xue. Improved algorithms for the bichromatic two-center problem for pairs of points. In Proceedings of the 16th Algorithms and Data Structures Symposium (WADS), pages 578-591, 2019. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact