2015/05/20 by Jean‐Daniel Boissonnat, Boissonnat, Jean-Daniel, Ramsay Dyer +3
Computer Science · #68W05 #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Management and Algorithms #FOS: Computer and information sciences #I.3.5 #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1505.05454
openalex publication_date 2015/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Computing Delaunay triangulations in \ℝd involves evaluating the\nso-called in\_sphere predicate that determines if a point x lies inside, on\nor outside the sphere circumscribing d+1 points p0,\… ,pd. This\npredicate reduces to evaluating the sign of a multivariate polynomial of degree\nd+2 in the coordinates of the points x, , p0, , \…, , pd. Despite\nmuch progress on exact geometric computing, the fact that the degree of the\npolynomial increases with d makes the evaluation of the sign of such a\npolynomial problematic except in very low dimensions. In this paper, we propose\na new approach that is based on the witness complex, a weak form of the\nDelaunay complex introduced by Carlsson and de Silva. The witness complex\n\Wit (L,W) is defined from two sets L and W in some metric space\nX: a finite set of points L on which the complex is built, and a set W of\nwitnesses that serves as an approximation of X. A fundamental result of de\nSilva states that \Wit(L,W)=\Del (L) if W=X=\ℝd.\nIn this paper, we give conditions on L that ensure that the witness complex\nand the Delaunay triangulation coincide when W is a finite set, and we\nintroduce a new perturbation scheme to compute a perturbed set L' close to\nL such that \Del (L')= \wit (L', W). Our perturbation\nalgorithm is a geometric application of the Moser-Tardos constructive proof of\nthe Lov 'asz local lemma. The only numerical operations we use are (squared)\ndistance comparisons (i.e., predicates of degree 2). The time-complexity of the\nalgorithm is sublinear in |W|. Interestingly, although the algorithm does not\ncompute any measure of simplex quality, a lower bound on the thickness of the\noutput simplices can be guaranteed.\n