New lower bounds for Hopcroft's problem

Discrete & Computational Geometry 16(4):389-418, 1996.
(Special issue of invited papers from the 11th Annual ACM Symposium on Computational Geometry)

Proceedings of the 11th Annual ACM Symposium on Computational Geometry, 127-137, 1995.

Technical Report A/04/94, Fachberiech Informatik, Universität des Saarlandes, Saarbrücken, Germany.


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 Rd, 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 Omega(n log m + n2/3m2/3 + m log n) in two dimensions, or Omega(n log m + n5/6m1/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 Matousek. Previously, the best known lower bound, in any dimension, was Omega(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. As a related result, using a straightforward adversary argument, we derive a quadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation.

Update (26 Sep 2000): Braß and Knauer, using recent work of Bárány, Harcos, Pach, and Tardos, recently discovered a set of n points and m hyperplanes, where at most d hyperplanes pass through any point, with a large number of point-hyperplane incidences. Their construction immediately improves my lower bound for Hopcroft's problem in d>2 dimensions to Omega(n log m + nd/(2d-1) m(2d-2)/(2d-1) + n(2d-2)/(2d-1) md/(2d-1) + m log n). This is an improvement for all n1/d << m << nd.
  1. Imre Bárány, Gergely Harcos, János Pach, and Gábor Tardos. Covering lattice points by subspaces. To appear in Period. Math. Hung.
  2. Peter Braß and Christian Knauer. Fast enumeration of point-hyperplane incidences. Technischer Bericht B 00-13, Freie Universität Berlin, Fachbereich Mathematik und Informatik, 2000.

Publications - Jeff Erickson (jeffe@cs.uiuc.edu) 14 Feb 2002