{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T05:49:45Z","timestamp":1791611385094,"version":"4.3.4"},"reference-count":26,"publisher":"World Scientific Pub Co Pte Lt","issue":"06","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[2000,12]]},"abstract":"<jats:p> Given a set P of n points in R<jats:sup>d<\/jats:sup>, 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 R<jats:sup>d<\/jats:sup>, 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. <\/jats:p>","DOI":"10.1142\/s0218195900000334","type":"journal-article","created":{"date-parts":[[2003,5,7]],"date-time":"2003-05-07T04:18:55Z","timestamp":1052281135000},"page":"593-608","source":"Crossref","is-referenced-by-count":11,"title":["QUANTILE APPROXIMATION FOR ROBUST STATISTICAL ESTIMATION AND k-ENCLOSING PROBLEMS"],"prefix":"10.1142","volume":"10","author":[{"given":"DAVID M.","family":"MOUNT","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Maryland, College Park, Maryland 20742, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"NATHAN S.","family":"NETANYAHU","sequence":"additional","affiliation":[{"name":"Dept. of Mathematics and Computer Science, Bar-Ilan University, Ramat-Gan 52900, Israel and Ctr. for Automation Research, University of Maryland, College Park, Maryland 20742, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"CHRISTINE D.","family":"PIATKO","sequence":"additional","affiliation":[{"name":"The Johns Hopkins University Applied Physics Laboratory, Laurel, Maryland 20723, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"RUTH","family":"SILVERMAN","sequence":"additional","affiliation":[{"name":"Center for Automation Research, University of Maryland, College Park, Maryland 20742, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"ANGELA Y.","family":"WU","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Information Systems, American University, Washington, DC 20016, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2012,4,30]]},"reference":[{"key":"p_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1038"},{"key":"p_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(91)90022-Q"},{"key":"p_5","doi-asserted-by":"publisher","DOI":"10.1016\/0167-7152(93)90145-9"},{"key":"p_6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0060"},{"key":"p_7","doi-asserted-by":"publisher","DOI":"10.1007\/BF01899996"},{"key":"p_14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574012"},{"key":"p_15","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009392"},{"key":"p_17","doi-asserted-by":"publisher","DOI":"10.1016\/0167-9473(93)90246-P"},{"key":"p_18","first-page":"95","volume":"8","author":"Hawkins D. M.","year":"1993","journal-title":"Computational Statistics"},{"key":"p_19","doi-asserted-by":"publisher","DOI":"10.1007\/BF02293051"},{"key":"p_20","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(94)00190-A"},{"key":"p_21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01940877"},{"key":"p_22","doi-asserted-by":"publisher","DOI":"10.1007\/BF00127126"},{"key":"p_23","first-page":"473","author":"Mount D. M.","year":"1997","journal-title":"Louisiana"},{"key":"p_24","doi-asserted-by":"publisher","DOI":"10.1016\/S0031-3203(96)00189-6"},{"key":"p_25","doi-asserted-by":"publisher","DOI":"10.1007\/BF00991005"},{"key":"p_26","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(86)90007-6"},{"key":"p_27","doi-asserted-by":"publisher","DOI":"10.2307\/2288718"},{"key":"p_29","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1990.10474920"},{"key":"p_32","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(97)00212-3"},{"key":"p_33","doi-asserted-by":"publisher","DOI":"10.1137\/0901028"},{"key":"p_34","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90030-L"},{"key":"p_38","first-page":"540","author":"Stein A.","year":"1992","journal-title":"Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Champaign, Illinois"},{"key":"p_39","doi-asserted-by":"publisher","DOI":"10.1109\/34.464558"},{"key":"p_42","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/62.2.313"},{"key":"p_45","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176350366"}],"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218195900000334","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T08:19:32Z","timestamp":1565079572000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218195900000334"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,12]]},"references-count":26,"journal-issue":{"issue":"06","published-online":{"date-parts":[[2012,4,30]]},"published-print":{"date-parts":[[2000,12]]}},"alternative-id":["10.1142\/S0218195900000334"],"URL":"https:\/\/doi.org\/10.1142\/s0218195900000334","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[2000,12]]}}}