Discrete Mathematics & Theoretical Computer Science, Vol 11, No 1 (2009)

Font Size:  Small  Medium  Large

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