Quantile approximation for robust statistical estimation and \(k\)-enclosing problems. (English) Zbl 0969.68168
Summary: Given a set \(P\) of \(n\) points in \(\mathbb R^d\), a fundamental problem in computational geometry is 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 \(\mathbb R^d\), 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.
MSC:
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
| 65D18 | Numerical aspects of computer graphics, image analysis, and computational geometry |
| 62G08 | Nonparametric regression and quantile regression |
| 62G35 | Nonparametric robustness |
Keywords:
robust estimation; LMS regression; minimum enclosing disk; minimum volume ball; minimum volume ellipsoid; minimum volume annulus estimatorReferences:
| [1] | DOI: 10.1006/jagm.1994.1038 · Zbl 1321.68425 · doi:10.1006/jagm.1994.1038 |
| [2] | DOI: 10.1016/0196-6774(91)90022-Q · Zbl 0715.68082 · doi:10.1016/0196-6774(91)90022-Q |
| [3] | DOI: 10.1016/0167-7152(93)90145-9 · doi:10.1016/0167-7152(93)90145-9 |
| [4] | DOI: 10.1006/jagm.1996.0060 · Zbl 0864.68040 · doi:10.1006/jagm.1996.0060 |
| [5] | DOI: 10.1007/BF01899996 · Zbl 0078.35803 · doi:10.1007/BF01899996 |
| [6] | DOI: 10.1007/BF02574012 · Zbl 0807.68094 · doi:10.1007/BF02574012 |
| [7] | DOI: 10.1007/PL00009392 · Zbl 0910.68219 · doi:10.1007/PL00009392 |
| [8] | DOI: 10.1016/0167-9473(93)90246-P · Zbl 0875.62305 · doi:10.1016/0167-9473(93)90246-P |
| [9] | Hawkins D. M., Computational Statistics 8 pp 95– (1993) |
| [10] | DOI: 10.1007/BF02293051 · Zbl 0752.68088 · doi:10.1007/BF02293051 |
| [11] | DOI: 10.1016/0020-0190(94)00190-A · Zbl 0875.68895 · doi:10.1016/0020-0190(94)00190-A |
| [12] | DOI: 10.1007/BF01940877 · Zbl 0857.68119 · doi:10.1007/BF01940877 |
| [13] | DOI: 10.1007/BF00127126 · doi:10.1007/BF00127126 |
| [14] | Mount D. M., Louisiana pp 473– (1997) |
| [15] | DOI: 10.1016/S0031-3203(96)00189-6 · doi:10.1016/S0031-3203(96)00189-6 |
| [16] | DOI: 10.1007/BF00991005 · Zbl 0582.68067 · doi:10.1007/BF00991005 |
| [17] | DOI: 10.1016/0196-6774(86)90007-6 · Zbl 0606.68038 · doi:10.1016/0196-6774(86)90007-6 |
| [18] | DOI: 10.2307/2288718 · Zbl 0547.62046 · doi:10.2307/2288718 |
| [19] | DOI: 10.1080/01621459.1990.10474920 · doi:10.1080/01621459.1990.10474920 |
| [20] | DOI: 10.1016/S0020-0190(97)00212-3 · Zbl 1338.68269 · doi:10.1016/S0020-0190(97)00212-3 |
| [21] | DOI: 10.1137/0901028 · Zbl 0469.52006 · doi:10.1137/0901028 |
| [22] | DOI: 10.1016/0020-0190(91)90030-L · Zbl 0713.68097 · doi:10.1016/0020-0190(91)90030-L |
| [23] | Stein A., Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Champaign, Illinois pp 540– (1992) |
| [24] | DOI: 10.1109/34.464558 · doi:10.1109/34.464558 |
| [25] | DOI: 10.1093/biomet/62.2.313 · Zbl 0308.62072 · doi:10.1093/biomet/62.2.313 |
| [26] | DOI: 10.1214/aos/1176350366 · Zbl 0624.62037 · doi:10.1214/aos/1176350366 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
