On center regions and balls containing many points

Smorodinsky S, Sulovský M, Wagner U. 2008. On center regions and balls containing many points. COCOON: Conference on Computing and Combinatorics, LNCS, vol. 5092, 363–373.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
Smorodinsky, Shakhar; Sulovský, Marek; Wagner, UliIST Austria
Series Title
LNCS
Abstract
We study the disk containment problem introduced by Neumann-Lara and Urrutia and its generalization to higher dimensions. We relate the problem to centerpoints and lower centerpoints of point sets. Moreover, we show that for any set of n points in ℝd, there is a subset A ⊆ S of size [d+3/2] such that any ball containing A contains at least roughly 4/5ed 3n points of S. This improves previous bounds for which the constant was exponentially small in d. We also consider a generalization of the planar disk containment problem to families of pseudodisks.
Publishing Year
Date Published
2008-01-01
Volume
5092
Page
363 - 373
Conference
COCOON: Conference on Computing and Combinatorics
IST-REx-ID

Cite this

Smorodinsky S, Sulovský M, Wagner U. On center regions and balls containing many points. In: Vol 5092. Springer; 2008:363-373. doi:10.1007/978-3-540-69733-6_36
Smorodinsky, S., Sulovský, M., & Wagner, U. (2008). On center regions and balls containing many points (Vol. 5092, pp. 363–373). Presented at the COCOON: Conference on Computing and Combinatorics, Springer. https://doi.org/10.1007/978-3-540-69733-6_36
Smorodinsky, Shakhar, Marek Sulovský, and Uli Wagner. “On Center Regions and Balls Containing Many Points,” 5092:363–73. Springer, 2008. https://doi.org/10.1007/978-3-540-69733-6_36.
S. Smorodinsky, M. Sulovský, and U. Wagner, “On center regions and balls containing many points,” presented at the COCOON: Conference on Computing and Combinatorics, 2008, vol. 5092, pp. 363–373.
Smorodinsky S, Sulovský M, Wagner U. 2008. On center regions and balls containing many points. COCOON: Conference on Computing and Combinatorics, LNCS, vol. 5092, 363–373.
Smorodinsky, Shakhar, et al. On Center Regions and Balls Containing Many Points. Vol. 5092, Springer, 2008, pp. 363–73, doi:10.1007/978-3-540-69733-6_36.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar