Optimal Higher Order Delaunay Triangulations of Polygons | SpringerLink
Skip to main content
Springer Nature Link
Log in

Optimal Higher Order Delaunay Triangulations of Polygons

  • Conference paper
LATIN 2008: Theoretical Informatics (LATIN 2008)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4957))

Included in the following conference series:

  • 1715 Accesses

Abstract

This paper presents an algorithm to triangulate polygons optimally using order-k Delaunay triangulations, for a number of quality measures. The algorithm uses properties of higher order Delaunay triangulations to improve the O(n 3) running time required for normal triangulations to O(k 2 n logk + knlogn) expected time, where n is the number of vertices of the polygon. An extension to polygons with points inside is also presented, allowing to compute an optimal triangulation of a polygon with h ≥ 1 components inside in O(knlogn) + O(k)h + 2 n expected time. Furthermore, through experimental results we show that, in practice, it can be used to triangulate point sets optimally for small values of k. This represents the first practical result on optimization of higher order Delaunay triangulations for k > 1.

This research has been partially funded by the Netherlands Organisation for Scientific Research (NWO) under the project GOGO.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Benkert, M., Gudmundsson, J., Haverkort, H.J., Wolff, A.: Constructing interference-minimal networks. In: Wiedermann, J., Tel, G., Pokorný, J., Bieliková, M., Štuller, J. (eds.) SOFSEM 2006. LNCS, vol. 3831, pp. 166–176. Springer, Heidelberg (2006)

    Chapter  Google Scholar 

  2. Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., Tan, T.S.: Edge insertion for optimal triangulations. Discrete Comput. Geom. 10(1), 47–65 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  3. Bern, M., Eppstein, D.: Mesh generation and optimal triangulation. In: Du, D.-Z., Hwang, F.K. (eds.) Computing in Euclidean Geometry, Lecture Notes Series on Computing, 2nd edn. vol. 4, pp. 47–123. World Scientific, Singapore (1995)

    Google Scholar 

  4. Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. ACM 39(1), 1–54 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  5. Chew, L.P.: Constrained Delaunay triangulations. Algorithmica 4, 97–108 (1989)

    Article  MATH  MathSciNet  Google Scholar 

  6. De Floriani, L., Falcidieno, B., Pienovi, C.: Delaunay-based representation of surfaces defined over arbitrarily shaped domains. Comput. Vision Graph. Image Process. 32, 127–140 (1985)

    Article  Google Scholar 

  7. de Kok, T., van Kreveld, M., Löffler, M.: Generating realistic terrains with higher-order Delaunay triangulations. Comp. Geom. Theory Appl. 36, 52–65 (2007)

    MATH  Google Scholar 

  8. Edelsbrunner, H., Tan, T.S.: A quadratic time algorithm for the minmax length triangulation. SIAM J. Comput. 22, 527–551 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  9. Fredman, M.L., Komlos, J., Szemeredi, E.: Storing a sparse table with O(1) worst case access time. J. ACM 31(3), 538–544 (1984)

    Article  MATH  MathSciNet  Google Scholar 

  10. Gilbert, P.D.: New results in planar triangulations. Report R-850, Coordinated Sci. Lab., Univ. Illinois, Urbana, IL (1979)

    Google Scholar 

  11. Gudmundsson, J., Hammar, M., van Kreveld, M.: Higher order Delaunay triangulations. Comput. Geom. Theory Appl. 23, 85–98 (2002)

    MATH  Google Scholar 

  12. Gudmundsson, J., Haverkort, H., van Kreveld, M.: Constrained higher order Delaunay triangulations. Comput. Geom. Theory Appl. 30, 271–277 (2005)

    MATH  Google Scholar 

  13. Hershberger, J., Suri, S.: A pedestrian approach to ray shooting: Shoot a ray, take a walk. J. Algorithms 18, 403–431 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  14. Keil, J.M., Vassilev, T.S.: Algorithms for optimal area triangulations of a convex polygon. Comput. Geom. Theory Appl. 35(3), 173–187 (2006)

    MATH  MathSciNet  Google Scholar 

  15. Klincsek, G.T.: Minimal triangulations of polygonal domains. Discrete Math. 9, 121–123 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  16. van Kreveld, M., Löffler, M., Silveira, R.I.: Optimization for first order Delaunay triangulations. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol. 4619, pp. 175–187. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  17. Levcopoulos, C., Krznaric, D.: The greedy triangulation can be computed from the Delaunay triangulation in linear time. Comput. Geom. Theory Appl. 14, 197–220 (1999)

    MATH  MathSciNet  Google Scholar 

  18. Mark, D.: Network models in geomorphology. In: Anderson, M.G. (ed.) Modelling Geomorphological Systems, ch. 4, pp. 73–97. John Wiley & Sons, Chichester (1988)

    Google Scholar 

  19. Mulzer, W., Rote, G.: Minimum weight triangulation is NP-hard. In: Proc. 22nd Annu. ACM Sympos. Comput. Geom., pp. 1–10 (2006)

    Google Scholar 

  20. Neamtu, M.: Delaunay configurations and multivariate splines: a generalization of a result of B. N. Delaunay. Trans. Amer. Math. Soc. 359(7), 2993–3004 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  21. Pebay, P.P., Baker, T.J.: A comparison of triangle quality measures. In: Proceedings of the 10th International Meshing Roundtable, pp. 327–340 (2001)

    Google Scholar 

  22. Silveira, R.I., van Kreveld, M.: Towards a Definition of Higher Order Constrained Delaunay Triangulations. In: Proceedings of the 19th Annual Canadian Conference on Computational Geometry (CCCG 2007), pp. 161–164 (2007)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Information and Computing Sciences, Utrecht University, 3508, TB Utrecht, The Netherlands

    Rodrigo I. Silveira & Marc van Kreveld

Authors
  1. Rodrigo I. Silveira
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Marc van Kreveld
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Eduardo Sany Laber Claudson Bornstein Loana Tito Nogueira Luerbio Faria

Rights and permissions

Reprints and permissions

Copyright information

© 2008 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Silveira, R.I., van Kreveld, M. (2008). Optimal Higher Order Delaunay Triangulations of Polygons. In: Laber, E.S., Bornstein, C., Nogueira, L.T., Faria, L. (eds) LATIN 2008: Theoretical Informatics. LATIN 2008. Lecture Notes in Computer Science, vol 4957. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-78773-0_12

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-78773-0_12

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-78772-3

  • Online ISBN: 978-3-540-78773-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation