Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

A probabilistic approach to reducing the algebraic complexity of computing 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 : Computing Delaunay triangulations in Rd involves evaluating the so-called in\_sphere predicate that determines if a point x lies inside, on or outside the sphere circumscribing d+1 points p0,...,pd. This predicate reduces to evaluating the sign of a multivariate polynomial of degree d+2in the coordinates of the points x, p0,... pd. Despite much progress on exact geometric computing, the fact that the degree of the polynomial increases with d makes the evaluation of the sign of such a polynomial problematic except in very low dimensions. In this paper, we propose a new approach that is based on the witness complex, a weak form of the Delaunay complex introduced by Carlsson and de Silva. The witness complex wit (L,W) is defined from two sets L and W in some metric space X: a finite set of points L on which the complex is built, and a set W of witnesses that serves as an approximation of X. A fundamental result of de Silva states that wit (L,W)= del (L) if W=X=Rd. In this paper, we give conditions on L that ensure that the witness complex and the Delaunay triangulation coincide when W is a finite set, and we introduce a new perturbation scheme to compute a perturbed set L' close to L such that del (L')= wit (L', W). Our perturbation algorithm is a geometric application of the Moser-Tardos constructive proof of the Lovàsz local lemma. The only numerical operations we use are (squared) distance comparisons (i.e., predicates of degree 2). The time-complexity of the algorithm is sublinear in |W|. Interestingly, although the algorithm does not compute any measure of simplex quality, a lower bound on the thickness of the output simplices can be guaranteed.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Jean-Daniel Boissonnat Connect in order to contact the contributor
Submitted on : Wednesday, May 20, 2015 - 6:49:48 PM
Last modification on : Thursday, January 20, 2022 - 5:27:41 PM
Long-term archiving on: : Thursday, April 20, 2017 - 5:51:19 AM


  • HAL Id : hal-01153979, version 1



Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh. A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations. 2015. ⟨hal-01153979⟩



Les métriques sont temporairement indisponibles