Selecting heavily covered points
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.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Chazelle, Bernard;
Edelsbrunner, HerbertISTA ;
Guibas, Leonidas;
Hershberger, John;
Seidel, Raimund;
Sharir, Micha
Abstract
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.
Publishing Year
Date Published
1994-12-01
Journal Title
SIAM Journal on Computing
Publisher
SIAM
Volume
23
Issue
6
Page
1138 - 1151
ISSN
IST-REx-ID
Cite this
Chazelle B, Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M. Selecting heavily covered points. SIAM Journal on Computing. 1994;23(6):1138-1151. doi:10.1137/S0097539790179919
Chazelle, B., Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., & Sharir, M. (1994). Selecting heavily covered points. SIAM Journal on Computing. SIAM. https://doi.org/10.1137/S0097539790179919
Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, John Hershberger, Raimund Seidel, and Micha Sharir. “Selecting Heavily Covered Points.” SIAM Journal on Computing. SIAM, 1994. https://doi.org/10.1137/S0097539790179919 .
B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, and M. Sharir, “Selecting heavily covered points,” SIAM Journal on Computing, 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.
Chazelle, Bernard, et al. “Selecting Heavily Covered Points.” SIAM Journal on Computing, vol. 23, no. 6, SIAM, 1994, pp. 1138–51, doi:10.1137/S0097539790179919 .
Link(s) to Main File(s)
Access Level
Closed Access