{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,21]],"date-time":"2026-11-21T07:53:57Z","timestamp":1795247637463,"version":"4.10.3"},"reference-count":18,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1994,12]]},"abstract":"<jats:p>A collection of geometric selection lemmas is proved, such as the following: For any set P of n points in three-dimensional space and any set S of m spheres, where each sphere passes through a distinct point pair in P, there exists a point x, not necessarily in P, that is enclosed by $\\Omega ({{m^2 } \/ {(n^2 \\log ^6 \\tfrac{{n^2 }}{m})}})$ of the spheres in S. Similar results apply in arbitrary fixed dimensions, and for geometric bodies other than spheres. The results have applications in reducing the size of geometric structures, such as three-dimensional Delaunay triangulations and Gabriel graphs, by adding extra points to their defining sets.<\/jats:p>","DOI":"10.1137\/s0097539790179919","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:39:46Z","timestamp":1109227186000},"page":"1138-1151","source":"Crossref","is-referenced-by-count":7,"title":["Selecting Heavily Covered Points"],"prefix":"10.1137","volume":"23","author":[{"given":"Bernard","family":"Chazelle","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Herbert","family":"Edelsbrunner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonidas J.","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John E.","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raimund","family":"Seidel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,13]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02574700"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1142\/9789814355858_0002"},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80059-5"},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1002\/nme.1620210210"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Chazelle, H. Edelsbrunner, L. J. Guibas, J. Hershberger, R. Seidel, M. Sharir,  Slimming down by adding; selecting heavily covered points, Tech Report, UIUCDCS-R-90-1574, Department of Computer Science, University of Illinois at Urbana-Champaign, Illinois,  1990, March","DOI":"10.1145\/98524.98551"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"L. P. Chew,  Guaranteed-quality triangular meshes, Tech. Report, TR-89-983, Department of Computer Science, Cornell University, Ithaca, NY,  1989","DOI":"10.21236\/ADA210101"},{"key":"R7","first-page":"793","volume":"7","author":"Delaunay B.","year":"1934","journal-title":"Izvestia Akademii Nauk SSSR, VII Seria, Otdelenie Matematicheskii i Estestvennyka Nauk"},{"key":"R8","first-page":"193","volume":"12","author":"Dewdney A. K.","year":"1977","journal-title":"Utilitas Math."},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1080\/00207168308803364"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-61568-9"},{"key":"R11","doi-asserted-by":"publisher","DOI":"10.1145\/77635.77639"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-65234-9"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.2307\/2412323"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"R15","first-page":"16","volume":"3","author":"Hopf H.","year":"1953","journal-title":"Math.-Phys. Semesterber."},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.1980.tb00031.x"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1098-6"},{"key":"R18","volume-title":"An analysis of the finite element method","author":"Strang Gilbert","year":"1973"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539790179919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:46:37Z","timestamp":1787337997000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539790179919"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":18,"journal-issue":{"issue":"6","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["10.1137\/S0097539790179919"],"URL":"https:\/\/doi.org\/10.1137\/s0097539790179919","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}