Centerpoint theorems for wedges

Jeff Erickson, Ferran Hurtado, Pat Morin

Research output: Contribution to journalArticle

Abstract

The Centerpoint Theorem states that, for any set S of n points in R d, there exists a point p in R 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 a. In M 2, we give bounds that are tight for all values of a and give an O(n) time algorithm to find a point satisfying these bounds. We also give partial results for R 3 and, more generally, R d.

Original languageEnglish (US)
Pages (from-to)45-54
Number of pages10
JournalDiscrete Mathematics and Theoretical Computer Science
Volume11
Issue number1
StatePublished - Jul 27 2009

Keywords

  • Centerpoint
  • Halfspace depth
  • Wedges

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)
  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Centerpoint theorems for wedges'. Together they form a unique fingerprint.

  • Cite this