TY - JOUR T1 - Quantile approximation for robust statistical estimation and k-enclosing problems JF - International Journal of Computational Geometry and Applications Y1 - 2000 A1 - Mount, Dave A1 - Netanyahu,N. S A1 - Piatko,C. D A1 - Silverman,R. A1 - Wu,A. Y AB - Given a set P of n points in Rd, a fundamental problem in computational geometryis concerned with finding the smallest shape of some type that encloses all the points of P. Well-known instances of this problem include finding the smallest enclosing box, minimum volume ball, and minimum volume annulus. In this paper we consider the following variant: Given a set of n points in Rd, find the smallest shape in question that contains at least k points or a certain quantile of the data. This type of problem is known as a k-enclosing problem. We present a simple algorithmic framework for computing quantile approximations for the minimum strip, ellipsoid, and annulus containing a given quantile of the points. The algorithms run in O(n log n) time. VL - 10 CP - 6 ER -