Document Open Access Logo

Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets

Authors Jean-Daniel Boissonnat, Olivier Devillers , Kunal Dutta , Marc Glisse

PDF
Thumbnail PDF

File

LIPIcs.ESA.2019.22.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Jean-Daniel Boissonnat
  • INRIA Sophia-Antipolis, Université Côte d’Azur, Nice, France
Olivier Devillers
  • INRIA, CNRS, Loria, Université de Lorraine, Nancy, France
Kunal Dutta
  • INRIA Sophia-Antipolis, Université Côte d’Azur, Nice, France
Marc Glisse
  • INRIA, Université Paris-Saclay, France

Funding

This work has been partially supported by the European Research Council under Advanced Grant 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions) and by grant ANR-17-CE40-0017 of the French National Research Agency (ANR project ASPAG).

Acknowledgements

The authors would like to acknowledge the referees for their helpful comments which helped to improve the presentation of the paper, in particular a simpler proof of Lemma 9.

Cite AsGet BibTex

Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, and Marc Glisse. Randomized Incremental Construction of Delaunay Triangulations of Nice Point Sets. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ESA.2019.22

Abstract

Randomized incremental construction (RIC) is one of the most important paradigms for building geometric data structures. Clarkson and Shor developed a general theory that led to numerous algorithms that are both simple and efficient in theory and in practice. Randomized incremental constructions are most of the time space and time optimal in the worst-case, as exemplified by the construction of convex hulls, Delaunay triangulations and arrangements of line segments. However, the worst-case scenario occurs rarely in practice and we would like to understand how RIC behaves when the input is nice in the sense that the associated output is significantly smaller than in the worst-case. For example, it is known that the Delaunay triangulations of nicely distributed points on polyhedral surfaces in E^3 has linear complexity, as opposed to a worst-case quadratic complexity. The standard analysis does not provide accurate bounds on the complexity of such cases and we aim at establishing such bounds in this paper. More precisely, we will show that, in the case of nicely distributed points on polyhedral surfaces, the complexity of the usual RIC is O(n log n), which is optimal. In other words, without any modification, RIC nicely adapts to good cases of practical value. Our proofs also work for some other notions of nicely distributed point sets, such as (epsilon, kappa)-samples. Along the way, we prove a probabilistic lemma for sampling without replacement, which may be of independent interest.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Randomized incremental construction
  • Delaunay triangulations
  • Voronoi diagrams
  • polyhedral surfaces
  • probabilistic analysis

Metrics

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

Related Versions

References

  1. N. Amenta and M. Bern. Surface Reconstruction by Voronoi Filtering. Discrete & Computational Geometry, 22(4):481-504, December 1999. Google Scholar
  2. Nina Amenta, Dominique Attali, and Olivier Devillers. Complexity of Delaunay triangulation for points on lower-dimensional polyhedra. In 18th ACM-SIAM Symposium on Discrete Algorithms, pages 1106-1113, 2007. Google Scholar
  3. Nina Amenta, Sunghee Choi, and Günter Rote. Incremental constructions con BRIO. In Proc. 19th Annual Symposium on Computational geometry, pages 211-219, 2003. URL: http://dx.doi.org/10.1145/777792.777824.
  4. Dominique Attali and Jean-Daniel Boissonnat. A Linear Bound on the Complexity of the Delaunay Triangulation of Points on Polyhedral Surfaces. Discrete & Computational Geometry, 31(3):369-384, February 2004. Google Scholar
  5. Dominique Attali, Jean-Daniel Boissonnat, and André Lieutier. Complexity of the Delaunay Triangulation of Points on Surfaces: the Smooth Case. In Proceedings of the Nineteenth Annual Symposium on Computational Geometry, SCG '03, pages 201-210, New York, NY, USA, 2003. ACM. URL: http://dx.doi.org/10.1145/777792.777823.
  6. Jean-Daniel Boissonnat and Frédéric Cazals. Smooth surface reconstruction via natural neighbour interpolation of distance functions. Computational Geometry, 22(1):185-203, 2002. 16th ACM Symposium on Computational Geometry. Google Scholar
  7. Jean-Daniel Boissonnat, Olivier Devillers, Kunal Dutta, and Marc Glisse. Randomized incremental construction of Delaunay triangulations of nice point sets. preprint, December 2018. URL: https://hal.inria.fr/hal-01950119.
  8. Jean-Daniel Boissonnat, Olivier Devillers, and Samuel Hornus. Incremental Construction of the Delaunay Triangulation and the Delaunay Graph in Medium Dimension. In Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, SCG '09, pages 208-216, New York, NY, USA, 2009. ACM. URL: http://dx.doi.org/10.1145/1542362.1542403.
  9. Jean-Daniel Boissonnat and Monique Teillaud. On the randomized construction of the Delaunay tree. Theoretical Computer Science, 112:339-354, 1993. URL: http://dx.doi.org/10.1016/0304-3975(93)90024-N.
  10. Keneth L. Clarkson and Peter W. Shor. Applications of random sampling in computational geometry, II. Discrete & Computational Geometry, 4:387-421, 1989. URL: http://dx.doi.org/10.1007/BF02187740.
  11. Olivier Devillers. Randomization Yields Simple O(n log^⋆ n) Algorithms for Difficult Ω(n) Problems. International Journal of Computational Geometry and Applications, 2(1):97-111, 1992. URL: https://hal.inria.fr/inria-00167206.
  12. Olivier Devillers. The Delaunay hierarchy. International Journal of Foundations of Computer Science, 13:163-180, 2002. URL: http://hal.inria.fr/inria-00166711.
  13. R.A. Dwyer. The expected number of k-faces of a Voronoi diagram. Computers & Mathematics with Applications, 26(5):13-19, 1993. Google Scholar
  14. Rex A. Dwyer. Higher-dimensional Voronoi diagrams in linear expected time. Discrete & Computational Geometry, 6(3):343-367, September 1991. Google Scholar
  15. Jeff Erickson. Nice Point Sets Can Have Nasty Delaunay Triangulations. In Proceedings of the Seventeenth Annual Symposium on Computational Geometry, SCG '01, pages 96-105, New York, NY, USA, 2001. ACM. Google Scholar
  16. Jeff Erickson. Dense Point Sets Have Sparse Delaunay Triangulations. Discrete & Computational Geometry, 33(1):83-115, January 2005. Google Scholar
  17. Mordecai J. Golin and Hyeon-Suk Na. On the average complexity of 3D-Voronoi diagrams of random points on convex polytopes. Computational Geometry, 25(3):197-231, 2003. Google Scholar
  18. J. L. Meijering. Interface area, edge length, and number of vertices in crystal aggregates with random nucleation. Philips Research Reports, 8:270-290, 1953. Google Scholar
  19. J. Møller. Random tessellations in ℝ^d. Advances in Applied Probability, 21(1):37–73, 1989. Google Scholar
  20. Rajeev Motwani and Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1995. Google Scholar
  21. Ketan Mulmuley. Computational geometry - an introduction through randomized algorithms. Prentice Hall, 1994. Google Scholar
  22. The CGAL Project. CGAL User and Reference Manual. CGAL Editorial Board, 4.14 edition, 2019. URL: https://doc.cgal.org/4.14/Manual/packages.html.
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