Quantile approximation for robust statistical estimation and k-enclosing problems

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.