Quantile approximation for robust statistical estimation and kappa-enclosing problems

Given a set P of n points in R-d, a fundamental problem in computational ge ometry is concerned with finding the smallest shape of some type that enclo ses all the points of P. Well-known instances of this problem include findi ng the smallest enclosing box, minimum volume ball, and minimum volume annu lus. In this paper we consider the following variant: Given a set of n poin ts in R-d, find the smallest shape in question that contains at least Ic po ints or a certain quantile of the data. This type of problem is known as a Ic-enclosing problem. We present a simple algorithmic framework for computi ng quantile approximations for the minimum strip, ellipsoid, and annulus co ntaining a given quantile of the points. The algorithms run in O(n log n) t ime.