Minimal set of constraints for 2D constrained Delaunay reconstruction

Abstract : Given a triangulation T of n points in the plane, we are interested in the minimal set of edges in T such that T can be reconstructed from this set (and the vertices of T) using constrained Delaunay triangulation. We show that this minimal set is precisely the set of non locally Delaunay edges, and that its cardinality is less than or equal to n+i/2 (if i is the number of interior points in T), which is a tight bound.
Type de document :
Article dans une revue
International Journal of Computational Geometry and Applications, World Scientific Publishing, 2003, 13 (5), pp.391-398. 〈10.1142/S0218195903001244〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00787186
Contributeur : Olivier Devillers <>
Soumis le : lundi 11 février 2013 - 15:19:21
Dernière modification le : samedi 27 janvier 2018 - 01:31:46

Lien texte intégral

Identifiants

Collections

Citation

Olivier Devillers, Regina Estkowski, Pierre-Marie Gandoin, Ferran Hurtado, Pedro Ramos, et al.. Minimal set of constraints for 2D constrained Delaunay reconstruction. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2003, 13 (5), pp.391-398. 〈10.1142/S0218195903001244〉. 〈hal-00787186〉

Partager

Métriques

Consultations de la notice

216