On center regions and balls containing many points Conference Paper


Author(s): Smorodinsky, Shakhar; Sulovský, Marek; Wagner, Uli
Title: On center regions and balls containing many points
Title Series: LNCS
Affiliation
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.
Keywords: point sets; Higher dimensions; Combinatorics; International conferences; Neumann
Conference Title: COCOON: Conference on Computing and Combinatorics
Volume: 5092
Conference Location: Dalian, China
ISBN: 978-354069732-9
Publisher: Springer  
Date Published: 2008-01-01
Start Page: 363
End Page: 373
DOI: 10.1007/978-3-540-69733-6_36
Open access: no
IST Austria Authors
  1. Uli Wagner
    50 Wagner
Related IST Austria Work