Document Open Access Logo

Dynamic Geometric Data Structures via Shallow Cuttings

Author Timothy M. Chan

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.24.pdf
  • Filesize: 475 kB
  • 13 pages

Document Identifiers

Author Details

Timothy M. Chan
  • Department of Computer Science, University of Illinois at Urbana-Champaign, USA

Funding

  • Chan, Timothy M.: Work supported in part by NSF Grant CCF-1814026.

Acknowledgements

I thank Sariel Har-Peled for discussions on other problems that indirectly led to the results of this paper. Thanks also to Mitchell Jones for discussions on range searching for points in convex position.

Cite As Get BibTex

Timothy M. Chan. Dynamic Geometric Data Structures via Shallow Cuttings. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 24:1-24:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.24

Abstract

We present new results on a number of fundamental problems about dynamic geometric data structures: 
1) We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v) the number of maximal (i.e., skyline) points in a 3D point set. The update times are near n^{11/12} for (i) and (ii), n^{7/8} for (iii) and (iv), and n^{2/3} for (v). Previously, sublinear bounds were known only for restricted "semi-online" settings [Chan, SODA 2002]. 
2) We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is O(log^2n), and the amortized update time is O(log^4n) instead of O(log^5n) [Chan, SODA 2006; Kaplan et al., SODA 2017]. 
3) We also improve previous fully dynamic data structures for maintaining the bichromatic closest pair between two 2D point sets and the diameter of a 2D point set. The amortized update time is O(log^4n) instead of O(log^7n) [Eppstein 1995; Chan, SODA 2006; Kaplan et al., SODA 2017].

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Theory of computation → Data structures design and analysis
Keywords
  • dynamic data structures
  • convex hulls
  • nearest neighbor search
  • closest pair
  • shallow cuttings

Metrics

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

Related Versions

References

  1. Peyman Afshani and Timothy M. Chan. Optimal halfspace range reporting in three dimensions. In Proc. 20th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 180-186, 2009. URL: http://dl.acm.org/citation.cfm?id=1496770.1496791.
  2. Pankaj K. Agarwal. Simplex range searching and its variants: A review. In M. Loebl, J. Nešetril, and R. Thomas, editors, Journal through Discrete Mathematics. Springer, to appear. Google Scholar
  3. Pankaj K. Agarwal and Jiří Matoušek. On range searching with semialgebraic sets. Discrete Comput. Geom., 11:393-418, 1994. URL: http://dx.doi.org/10.1007/BF02574015.
  4. Pankaj K. Agarwal and Jiří Matoušek. Dynamic half-space range reporting and its applications. Algorithmica, 13(4):325-345, 1995. URL: http://dx.doi.org/10.1007/BF01293483.
  5. Jon Louis Bentley and James B. Saxe. Decomposable searching problems I: static-to-dynamic transformation. J. Algorithms, 1(4):301-358, 1980. URL: http://dx.doi.org/10.1016/0196-6774(80)90015-2.
  6. Gerth Stølting Brodal and Riko Jacob. Dynamic planar convex hull. In Proc. 43rd Sympos. Found. Comput. Sci. (FOCS), pages 617-626, 2002. URL: http://dx.doi.org/10.1109/SFCS.2002.1181985.
  7. Timothy M. Chan. Dynamic planar convex hull operations in near-logarithmic amortized time. J. ACM, 48(1):1-12, 2001. Preliminary version in FOCS 1999. URL: http://dx.doi.org/10.1145/363647.363652.
  8. Timothy M. Chan. A fully dynamic algorithm for planar width. Discrete Comput. Geom., 30(1):17-24, 2003. Preliminary version in SoCG 2001. URL: http://dx.doi.org/10.1007/s00454-003-2923-8.
  9. Timothy M. Chan. Semi-online maintenance of geometric optima and measures. SIAM J. Comput., 32(3):700-716, 2003. Preliminary version in SODA 2002. URL: http://dx.doi.org/10.1137/S0097539702404389.
  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. Preliminary version in SODA 2006. URL: http://dx.doi.org/10.1145/1706591.1706596.
  11. Timothy M. Chan. Optimal partition trees. Discrete Comput. Geom., 47(4):661-690, 2012. Preliminary version in SoCG 2010. URL: http://dx.doi.org/10.1007/s00454-012-9410-z.
  12. Timothy M. Chan. Three problems about dynamic convex hulls. Int. J. Comput. Geom. Appl., 22(4):341-364, 2012. Preliminary version in SoCG 2011. URL: http://dx.doi.org/10.1142/S0218195912600096.
  13. Timothy M. Chan, Kasper Green Larsen, and Mihai Pătraşcu. Orthogonal range searching on the RAM, revisited. In Proc. 27th ACM Sympos. Comput. Geom. (SoCG), pages 1-10, 2011. URL: http://dx.doi.org/10.1145/1998196.1998198.
  14. Timothy M. Chan, Mihai Pătraşcu, and Liam Roditty. Dynamic connectivity: Connecting to networks and geometry. SIAM J. Comput., 40(2):333-349, 2011. Preliminary version in FOCS 2008. URL: http://dx.doi.org/10.1137/090751670.
  15. Timothy M. Chan and Konstantinos Tsakalidis. Optimal deterministic algorithms for 2-d and 3-d shallow cuttings. Discrete Comput. Geom., 56(4):866-881, 2016. Preliminary version in SoCG 2015. URL: http://dx.doi.org/10.1007/s00454-016-9784-4.
  16. Mark de Berg, Otfried Cheong, Marc J. van Kreveld, and Mark H. Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition, 2008. URL: http://www.worldcat.org/oclc/227584184.
  17. David P. Dobkin and Subhash Suri. Maintenance of geometric extrema. J. ACM, 38(2):275-298, 1991. URL: http://dx.doi.org/10.1145/103516.103518.
  18. David Eppstein. Dynamic Euclidean minimum spanning trees and extrema of binary functions. Discrete Comput. Geom., 13:111-122, 1995. URL: http://dx.doi.org/10.1007/BF02574030.
  19. David Eppstein. Fast hierarchical clustering and other applications of dynamic closest pairs. ACM Journal of Experimental Algorithmics, 5:1, 2000. URL: http://dx.doi.org/10.1145/351827.351829.
  20. Jacob Holm, Eva Rotenberg, and Christian Wulff-Nilsen. Faster fully-dynamic minimum spanning forest. In Proc. 23rd European Sympos. Algorithms (ESA), pages 742-753, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48350-3_62.
  21. Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth, and Micha Sharir. Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications. In Proc. 28th ACM-SIAM Sympos. Discrete Algorithms (SODA), pages 2495-2504, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.165.
  22. Jiří Matoušek. Efficient partition trees. Discrete Comput. Geom., 8:315-334, 1992. URL: http://dx.doi.org/10.1007/BF02293051.
  23. Jiří Matoušek. Reporting points in halfspaces. Comput. Geom. Theory Appl., 2:169-186, 1992. URL: http://dx.doi.org/10.1016/0925-7721(92)90006-E.
  24. Mark H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer, 1983. URL: http://dx.doi.org/10.1007/BFb0014927.
  25. Mark H. Overmars and Jan van Leeuwen. Maintenance of configurations in the plane. J. Comput. Syst. Sci., 23(2):166-204, 1981. URL: http://dx.doi.org/10.1016/0022-0000(81)90012-X.
  26. Edgar A. Ramos. On range reporting, ray shooting and k-level construction. In Proc. 15th Sympos. Comput. Geom. (SoCG), pages 390-399, 1999. URL: http://dx.doi.org/10.1145/304893.304993.
  27. Micha Sharir and Shai Zaban. Output-sensitive tools for range searching in higher dimensions. Manuscript, 2013. URL: http://www.cs.tau.ac.il/~michas/shai.pdf.
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 About DROPS Imprint Privacy Contact