Donald Bren School of Information and Computer Sciences
New algorithms for minimum-measure simplices and one-dimensional weighted Voronoi diagrams
- Author(s): Eppstein, David
- Erickson, Jeff
- et al.
We present two new algorithms for finding the minimum-measure simplex determined by a set of n points in R^d for arbitrary d >/= 2. The first algorithm runs in time O(n^d log n) using O(n) space. The only data structure used by this algorithms a stack. The second algorithm runs in time O(n^d) using O(n^2) space, which matches the best known time bounds for this problem in all dimensions and exceeds the previous best space bounds for all d > 3. We also present a new optimal algorithm for building one-dimensional multiplicatively weighted Voronoi diagrams that runs in linear time if the points are already sorted.