A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations

Jean-Daniel Boissonnat 1 Ramsay Dyer 2 Arijit Ghosh 3
1 GEOMETRICA - Geometric computing
CRISAM - Inria Sophia Antipolis - Méditerranée , Inria Saclay - Ile de France
3 Algorithms and Complexity
MPII - Max-Planck-Institut für Informatik
Abstract : We propose algorithms to compute the Delaunay triangulation of a point set L using only (squared) distance comparisons (i.e., predicates of degree 2). Our approach is based on the witness complex, a weak form of the Delaunay complex introduced by Carlsson and de Silva. We give conditions that ensure that the witness complex and the Delaunay triangulation coincide and we introduce a new perturbation scheme to compute a perturbed set L′ close to L such that the Delaunay triangulation and the witness complex coincide. Our perturbation algorithm is a geometric application of the Moser-Tardos constructive proof of the Lovász local lemma.
Type de document :
Communication dans un congrès
Nikhil Bansal and Irene Finocchi. Algorithms - ESA 2015, Sep 2015, Patras, Greece. Springer, 9294, pp.595-606, 2015, Lecture Notes in Computer Science. 〈http://algo2015.upatras.gr/esa/〉. 〈10.1007/978-3-662-48350-3_50〉
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger


https://hal.inria.fr/hal-01213070
Contributeur : Jean-Daniel Boissonnat <>
Soumis le : mercredi 7 octobre 2015 - 17:05:39
Dernière modification le : mardi 21 novembre 2017 - 01:22:44
Document(s) archivé(s) le : vendredi 8 janvier 2016 - 10:50:46

Fichiers

esa.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations. Nikhil Bansal and Irene Finocchi. Algorithms - ESA 2015, Sep 2015, Patras, Greece. Springer, 9294, pp.595-606, 2015, Lecture Notes in Computer Science. 〈http://algo2015.upatras.gr/esa/〉. 〈10.1007/978-3-662-48350-3_50〉. 〈hal-01213070〉

Partager

Métriques

Consultations de la notice

222

Téléchargements de fichiers

103