Selecting heavily covered points

B. Chazelle, H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, SIAM Journal on Computing 23 (1994) 1138–1151.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ; ;
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
Volume
23
Issue
6
Page
1138 - 1151
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, 23(6), 1138–1151. 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 23, no. 6 (1994): 1138–51. 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, 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 .

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar