Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [13 references]  Display  Hide  Download
Contributor : Jean-Daniel Boissonnat <>
Submitted on : Wednesday, October 7, 2015 - 5:05:39 PM
Last modification on : Tuesday, April 30, 2019 - 5:14:02 PM
Long-term archiving on: : Friday, January 8, 2016 - 10:50:46 AM


Files produced by the author(s)




Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations. Algorithms - ESA 2015, Sep 2015, Patras, Greece. pp.595-606, ⟨10.1007/978-3-662-48350-3_50⟩. ⟨hal-01213070⟩



Record views


Files downloads