one-dimensional weighted Voronoi diagrams

U.C. Irvine Technical Report 92-55, June 1992.

- Sorry, nothing to download. Send me email if you would like a copy.

Abstract:

We present two new algorithms for finding the minimum-measure simplex determined by a set ofnpoints in, for arbitraryR^{d}d\ge 2. The first algorithm runs in timeO(nlog^{d}n)usingO(n)space. The only data structure used by this algorithm is a stack. The second algorithm runs in timeO(nusing^{d})O(nspace, which matches the best known time bounds for this problem in all dimensions and exceeds the previous best space bounds for all^{2})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.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 15 Nov 1999