article published yes Bernard Chazelle author Herbert Edelsbrunner author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833 Leonidas Guibas author John Hershberger author Raimund Seidel author Micha Sharir author 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 Ω(m2/(n2 log6 n2/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. SIAM1994 eng 0097-539710.1137/S0097539790179919 2361138 - 1151 yes Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger, Raimund Seidel, and Micha Sharir. “Selecting Heavily Covered Points.” <i>SIAM Journal on Computing</i>. SIAM, 1994. <a href="https://doi.org/10.1137/S0097539790179919 ">https://doi.org/10.1137/S0097539790179919 </a>. Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., &#38; Sharir, M. (1994). Selecting heavily covered points. <i>SIAM Journal on Computing</i>. SIAM. <a href="https://doi.org/10.1137/S0097539790179919 ">https://doi.org/10.1137/S0097539790179919 </a> Chazelle, Bernard, et al. “Selecting Heavily Covered Points.” <i>SIAM Journal on Computing</i>, vol. 23, no. 6, SIAM, 1994, pp. 1138–51, doi:<a href="https://doi.org/10.1137/S0097539790179919 ">10.1137/S0097539790179919 </a>. B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M. Sharir, “Selecting heavily covered points,” <i>SIAM Journal on Computing</i>, vol. 23, no. 6. SIAM, pp. 1138–1151, 1994. Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. 1994. Selecting heavily covered points. SIAM Journal on Computing. 23(6), 1138–1151. B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, SIAM Journal on Computing 23 (1994) 1138–1151. Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Selecting heavily covered points. <i>SIAM Journal on Computing</i>. 1994;23(6):1138-1151. doi:<a href="https://doi.org/10.1137/S0097539790179919 ">10.1137/S0097539790179919 </a> 40332018-12-11T12:06:33Z2022-06-03T06:41:56Z