de.mpg.escidoc.pubman.appbase.FacesBean
English

Item

ITEM ACTIONSEXPORT

Released

Paper

A Probabilistic Approach to Reducing the Algebraic Complexity of Computing Delaunay Triangulations

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons101795

Ghosh,  Arijit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1505.05454.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Boissonnat, J.-D., Dyer, R., & Ghosh, A. (2015). A Probabilistic Approach to Reducing the Algebraic Complexity of Computing Delaunay Triangulations. Retrieved from http://arxiv.org/abs/1505.05454.

Cite as: http://hdl.handle.net/11858/00-001M-0000-0028-6694-0
Abstract
Computing Delaunay triangulations in $\mathbb{R}^d$ 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 $p_0,\ldots ,p_d$. This predicate reduces to evaluating the sign of a multivariate polynomial of degree $d+2$ in the coordinates of the points $x, \, p_0,\, \ldots,\, p_d$. 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 $\mathrm{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 $\mathrm{Wit}(L,W)=\mathrm{Del} (L)$ if $W=X=\mathbb{R}^d$. 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 $\mathrm{Del} (L')= \mathrm{wit} (L', W)$. Our perturbation algorithm is a geometric application of the Moser-Tardos constructive proof of the Lov\'asz 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.