Better lower bounds on detecting affine and spherical degeneracies

J. Erickson, R. Seidel

Research output: Contribution to journalArticlepeer-review


We show that in the worst case, Ω(n d ) sidedness queries are required to determine whether a set of n points in ℝ d is affinely degenerate, i.e., whether it contains d+1 points on a common hyperplane. This matches known upper bounds. We give a straightforward adversary argument, based on the explicit construction of a point set containing Ω(n d ) "collapsible" simplices, any one of which can be made degenerate without changing the orientation of any other simplex. As an immediate corollary, we have an Ω(n d ) lower bound on the number of sidedness queries required to determine the order type of a set of n points in ℝ d . Using similar techniques, we also show that Ω(n d+1) in-sphere queries are required to decide the existence of spherical degeneracies in a set of n points in ℝ d .

Original languageEnglish (US)
Pages (from-to)41-57
Number of pages17
JournalDiscrete & Computational Geometry
Issue number1
StatePublished - Dec 1995
Externally publishedYes

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


Dive into the research topics of 'Better lower bounds on detecting affine and spherical degeneracies'. Together they form a unique fingerprint.

Cite this