{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,11]],"date-time":"2026-03-11T13:29:22Z","timestamp":1773235762261,"version":"3.50.1"},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Comput. Geom. Appl."],"published-print":{"date-parts":[[1996,9]]},"abstract":"<jats:p> We give a practical and provably good Monte Carlo algorithm for approximating center points. Let P be a set of n points in R<jats:sup>d<\/jats:sup>. A point c\u2208R<jats:sup>d<\/jats:sup> is a \u03b2-center point of P if every closed halfspace containing c contains at least \u03b2n points of P. Every point set has a 1\/(d+1)-center point; our algorithm finds an \u03a9(1\/d<jats:sup>2<\/jats:sup>)-center point with high probability. Our algorithm has a small constant factor and is the first approximate center point algorithm whose complexity is subexponential in d. Moreover, it can be optimally parallelized to require O( log <jats:sup>2<\/jats:sup>d log log n) time. Our algorithm has been used in mesh partitioning methods and can be used in the construction of high breakdown estimators for multivariate datasets in statistics. It has the potential to improve results in practice for constructing weak \u220a-nets. We derive a variant of our algorithm whose time bound is fully polynomial in d and linear in n, and show how to combine our approach with previous techniques to compute high quality center points more quickly. <\/jats:p>","DOI":"10.1142\/s021819599600023x","type":"journal-article","created":{"date-parts":[[2004,9,6]],"date-time":"2004-09-06T11:50:09Z","timestamp":1094471409000},"page":"357-377","source":"Crossref","is-referenced-by-count":52,"title":["APPROXIMATING CENTER POINTS WITH ITERATIVE RADON POINTS"],"prefix":"10.1142","volume":"06","author":[{"given":"KENNETH L.","family":"CLARKSON","sequence":"first","affiliation":[{"name":"AT&amp;T Bell Laboratories,MurrayHill, New Jersy 07974, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"DAVID","family":"EPPSTEIN","sequence":"additional","affiliation":[{"name":"Department of Information and Computer Science, University of California, Irvine, California 92717, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"GARY L.","family":"MILLER","sequence":"additional","affiliation":[{"name":"School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CARL","family":"STURTIVANT","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Minnesota, Minneapolis, Minnesota, 55455, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"SHANG-HUA","family":"TENG","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Massachusetts Institute of Technology, Cambridge, Massachusetts, 02139, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"container-title":["International Journal of Computational Geometry &amp; Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S021819599600023X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T15:37:42Z","timestamp":1565192262000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S021819599600023X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[1996,9]]}},"alternative-id":["10.1142\/S021819599600023X"],"URL":"https:\/\/doi.org\/10.1142\/s021819599600023x","relation":{},"ISSN":["0218-1959","1793-6357"],"issn-type":[{"value":"0218-1959","type":"print"},{"value":"1793-6357","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,9]]}}}