Triangulating point sets in space (Q1820437)

Let P be a set of n points in \(R^ d\), whose convex hull is a d-simplex. If there are n' interior points, the authors give an algorithm for finding a splitter, which is one of these points which splits conv P into \(d+1\) simplices, none of which contains more than \(dn'/(d+1)\) points, in time \(O(d^ 4+nd^ 2)\). Using this result, they can triangulate a set of n points in general position in \(R^ d\) in time \(O(nd^ 4\log_{1+1/d}n)\). There is an improved algorithm in \(R^ 3\).