On center regions and balls containing many points Academic Article uri icon

abstract

  • 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, there is a subset A⊆ S of size ⌊d+32⌋ such that any ball containing A contains at least roughly 45ed^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.

publication date

  • January 1, 2008