Donald Bren School of Information and Computer Sciences

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.