New lower bounds for Hopcroft's problem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set of n points and m hyperplanes in IRd, is any point contained in any hyperplane? We define a general class of partitioning algorithms, and show that in the worst case, for all m and n, any such algorithm requires time Ω(n log m + n2/3 m2/3 + m log n) in two dimensions, or Ω(n log m + n5/6 m1/2 + n1/2m5/6 + m log n) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcroft's problem in four or more dimensions. Our planar lower bound is within a factor of 2O(log∗(n+m)) of the best known upper bound, due to Matoušek. Previously, the best known lower bound, in any dimension, was Ω(n log m + m log n). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called a monochromatic cover, and derive lower bounds on the complexity of this representation. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover.

Original languageEnglish (US)
Title of host publicationProceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995
PublisherAssociation for Computing Machinery
Pages127-137
Number of pages11
ISBN (Electronic)0897917243
DOIs
StatePublished - Sep 1 1995
Externally publishedYes
Event11th Annual Symposium on Computational Geometry, SCG 1995 - Vancouver, Canada
Duration: Jun 5 1995Jun 7 1995

Publication series

NameProceedings of the Annual Symposium on Computational Geometry
VolumePart F129372

Other

Other11th Annual Symposium on Computational Geometry, SCG 1995
CountryCanada
CityVancouver
Period6/5/956/7/95

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'New lower bounds for Hopcroft's problem'. Together they form a unique fingerprint.

  • Cite this

    Erickson, J. (1995). New lower bounds for Hopcroft's problem. In Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995 (pp. 127-137). (Proceedings of the Annual Symposium on Computational Geometry; Vol. Part F129372). Association for Computing Machinery. https://doi.org/10.1145/220279.220293