More Output-Sensitive Geometric Algorithms (Extended Abstract)
Kenneth L. Clarkson · 1994
A simple idea for speeding up the computation of extrema of a partially ordered set turns out to have a number of interesting applications in geometric algorithms; the resulting algorithms generally replace an appearance of the input size n in the running time by an output size A n. In particular, the A coordinate-wise minima of a set of n points in R d can be found by an algorithm needing O(nA) time. Given n points uniformly distributed in the unit square, the algorithm needs n + O(n 5=8 ) point comparisons on average. Given a set of n points in R d , another algorithm can find its A extreme points in O(nA) time. Thinning for nearest-neighbor classification can be done in time O(n log n) P i A i n i , finding the A i irredundant points among n i points for each class i, where n = P i n i is the total number of input points. This sharpens a more obvious O(n 3 ) algorithm, which is also given here. Another algorithm is given that needs O(n) space to compute the convex ...