TY - GEN

T1 - New lower bounds for Hopcroft's problem

AU - Erickson, Jeff

N1 - Funding Information:
*This research was partially supported by NSF grant CCR-9058440. An earlier version of this paper was published as Technical Report A/04/94, Fachbereich Inforrnatik, Universitat des Saarlandes, Saarbriicken, Germany, November 1994.
Publisher Copyright:
© 1995 ACM.

PY - 1995/9/1

Y1 - 1995/9/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84968398176&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84968398176&partnerID=8YFLogxK

U2 - 10.1145/220279.220293

DO - 10.1145/220279.220293

M3 - Conference contribution

AN - SCOPUS:84968398176

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 127

EP - 137

BT - Proceedings of the 11th Annual Symposium on Computational Geometry, SCG 1995

PB - Association for Computing Machinery

T2 - 11th Annual Symposium on Computational Geometry, SCG 1995

Y2 - 5 June 1995 through 7 June 1995

ER -