A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations - Archive ouverte HAL Access content directly
Conference Papers Year : 2015

A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations

(1) , (2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
esa.pdf (316.36 Ko) Télécharger le fichier
Vignette du fichier
witness-complex.jpg (24.5 Ko) Télécharger le fichier
Vignette du fichier
witness-complex.png (35.65 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Format : Figure, Image
Origin : Files produced by the author(s)
Format : Figure, Image
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01213070 , version 1 (07-10-2015)

Identifiers

Cite

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⟩
439 View
146 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More