Triangulating simplicial point sets in space

A set P of points in R^d is called simplicial if it has dimension d and contains exactly d + 1 extreme points. We show that when P contains n interior points, there is always one point, called a splitter, that partitions P into d + 1 simplices, none of which contain more than dn /(d + 1) points. A splitter can be found in Ο (d⁴n) time. Using this result, we give a Ο (d⁴n log_1+1/d n) algorithm for triangulating simplicial point sets that are in general position. In R³ we give an Ο (n logn + k) algorithm for triangulating arbitrary point sets, where k is the number of simplices produced. We exhibit sets of 2n + 1 points in R³ for which the number of simplices produced may vary between (n -1)² + 1 and 2n -2. We also exhibit point sets for which every triangulation contains a quadratic number of simplices.