A probabilistic approach to reducing the algebraic complexity of computing Delaunay triangulations

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh

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 circ…