Centerpoint Theorems for Wedges
Jeff Erickson, Ferran Hurtado, Pat Morin
Abstract
The Centerpoint Theorem states that, for any set
S
of n points in ℝd, there
exists
a point p in ℝd such that
every
closed halfspace containing p contains at least
n/(d+1)
points of S. We consider generalizations of the
Centerpoint
Theorem in which halfspaces are replaced with wedges (cones) of angle
α.
In ℝ2, we give bounds that are tight for
all
values of α and give an O(n) time
algorithm
to find a point satisfying these bounds. We also give partial results
for
ℝ3 and, more generally,
ℝd.
Full Text: PDF PostScript