Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead

Authors Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, Wolfgang Mulzer



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.26.pdf
  • Filesize: 0.79 MB
  • 15 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
  • Department of Computer Science, Duke University, Durham, NC 27708, USA
Ravid Cohen
  • School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
Dan Halperin
  • School of Computer Science, Tel-Aviv University, Tel-Aviv 69978, Israel
Wolfgang Mulzer
  • Institut für Informatik, Freie Universität Berlin, 14195 Berlin, Germany

Acknowledgements

We thank Haim Kaplan and Micha Sharir for helpful disucussions.

Cite AsGet BibTex

Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer. Maintaining the Union of Unit Discs Under Insertions with Near-Optimal Overhead. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.26

Abstract

We present efficient data structures for problems on unit discs and arcs of their boundary in the plane. (i) We give an output-sensitive algorithm for the dynamic maintenance of the union of n unit discs under insertions in O(k log^2 n) update time and O(n) space, where k is the combinatorial complexity of the structural change in the union due to the insertion of the new disc. (ii) As part of the solution of (i) we devise a fully dynamic data structure for the maintenance of lower envelopes of pseudo-lines, which we believe is of independent interest. The structure has O(log^2 n) update time and O(log n) vertical ray shooting query time. To achieve this performance, we devise a new algorithm for finding the intersection between two lower envelopes of pseudo-lines in O(log n) time, using tentative binary search; the lower envelopes are special in that at x=-infty any pseudo-line contributing to the first envelope lies below every pseudo-line contributing to the second envelope. (iii) We also present a dynamic range searching structure for a set of circular arcs of unit radius (not necessarily on the boundary of the union of the corresponding discs), where the ranges are unit discs, with O(n log n) preprocessing time, O(n^{1/2+epsilon} + l) query time and O(log^2 n) amortized update time, where l is the size of the output and for any epsilon>0. The structure requires O(n) storage space.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • lower envelopes
  • pseudo-lines
  • unit discs
  • range search
  • dynamic algorithms
  • tentative binary search

Metrics

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

References

  1. Pankaj K. Agarwal. Range searching. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 40. Chapman &Hall/CRC, 3rd edition, 2017. Google Scholar
  2. Pankaj K. Agarwal. Simplex Range Searching and Its Variants: A Review, pages 1-30. Springer International Publishing, Cham, 2017. Google Scholar
  3. Pankaj K. Agarwal, Ravid Cohen, Dan Halperin, and Wolfgang Mulzer. Maintaining the Union of Unit Discs under Insertions with Near-Optimal Overhead, 2019. URL: http://arxiv.org/abs/1903.10943v1.
  4. Pankaj. K. Agarwal and Jiří Matoušek. On range searching with semialgebraic sets. Discrete & Computational Geometry, 11(4):393-418, 1994. Google Scholar
  5. Pankaj K. Agarwal and Jiří Matoušek. Dynamic Half-Space Range Reporting and Its Applications. Algorithmica, 13(4):325-345, 1995. Google Scholar
  6. F. Aurenhammer. Improved algorithms for discs and balls using power diagrams. Journal of Algorithms, 9(2):151-161, 1988. URL: http://dx.doi.org/10.1016/0196-6774(88)90035-1.
  7. Gerth Stølting Brodal and Riko Jacob. Dynamic Planar Convex Hull with Optimal Query Time. In Algorithm Theory - SWAT 2000, 7th Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 5-7, 2000, Proceedings, pages 57-70, 2000. Google Scholar
  8. Gerth Stølting Brodal and Riko Jacob. Dynamic Planar Convex Hull. In Proceedings of the 43rd Symposium on Foundations of Computer Science, pages 617-626, 2002. Google Scholar
  9. Timothy M. Chan. Dynamic planar convex hull operations in near-logarithmaic amortized time. J. ACM, 48(1):1-12, 2001. Google Scholar
  10. Timothy M. Chan. A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries. J. ACM, 57(3):16:1-16:15, 2010. Google Scholar
  11. Ravid Cohen, Dan Halperin, and Yossi Yovel. Sensory Regimes of Effective Distributed Searching without Leaders. Manuscript, 2018. Google Scholar
  12. Mark de Berg, Kevin Buchin, Bart MP Jansen, and Gerhard Woeginger. Fine-grained complexity analysis of two classic TSP variants. arXiv preprint, 2016. URL: http://arxiv.org/abs/1607.02725.
  13. Dan Halperin and Mark H. Overmars. Spheres, molecules, and hidden surface removal. Comput. Geom., 11(2):83-102, 1998. Google Scholar
  14. Dan Halperin and Micha Sharir. Arrangements. In Jacob E. Goodman, Joseph O'Rourke, and Csaba Tóth, editors, Handbook of Discrete and Computational Geometry, chapter 28. Chapman &Hall/CRC, 3rd edition, 2017. Google Scholar
  15. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2495-2504, 2017. Google Scholar
  16. Haim Kaplan, Robert Endre Tarjan, and Kostas Tsioutsiouliklis. Faster kinetic heaps and their use in broadcast scheduling. In Proceedings of the 12th Annual Symposium on Discrete Algorithms, pages 836-844, 2001. Google Scholar
  17. Klara Kedem, Ron Livne, János Pach, and Micha Sharir. On the Union of Jordan Regions and Collision-Free Translational Motion Amidst Polygonal Obstacles. Discrete & Computational Geometry, 1:59-70, 1986. Google Scholar
  18. Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. Journal of Computer and System Sciences, 23(2):166-204, 1981. Google Scholar
  19. Franco P. Preparata and Michael Ian Shamos. Computational Geometry. An Introduction. Springer-Verlag, New York, 1985. Google Scholar
  20. Paul G Spirakis. Very fast algorithms for the area of the union of many circles. Report no. 98 - Dept. Computer Science, Courant Institute, New York University, 1983. 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