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 ...