new techniques for computing order statistics in euclidean space (extended abstract)
Given a finite point-set S in E 2 , how hard is it to compute the &kgr; th largest interdistance, or say, the &kgr; th largest slope or &kgr; th largest triangular area formed by points of S ? We examine the complexity of a general class of problems built from these examples, and present a number of techniques for deriving nontrivial upper bounds. Surprisingly, these bounds often match or come very close to the complexity of the corresponding extremal problems (e.g. computing the largest or smallest interdistance, slope, etc.)
computation order statistics space abstraction point complexity general class examples matching