Abstract
We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set ofn points andm hyperplanes in\(\mathbb{R}^d \), is any point contained in any hyperplane? We define a general class ofpartitioning algorithms, and show that in the worst case, for allm andn, any such algorithm requires time Ω(n logm + n 2/3m2/3 + m logn) in two dimensions, or Ω(n logm + n 5/6m1/2 + n1/2m5/6 + m logn) 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 logm + m logn). 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 amonochromatic cover, and derive lower bounds on its size in the worst case. 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 aquadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
P. K. Agarwal. Partitioning arrangements of lines: II. Applications.Discrete Comput. Geom., 5:533–573, 1990.
P. K. Agarwal, N. Alon, B. Aronov, and S. Suri. Can visibility graphs be represented compactly?Proc. 9th Ann. ACM Symp. on Computational Geometry, pages 338–347, 1993.
M. Ben-Or. Lower bounds for algebraic computation trees.Proc. 15th Ann. ACM Symp. on Theory of Computing, pages 80–86, 1983.
M. de Berg, M. Overmars, and O. Schwarzkopf. Computing and verifying depth orders.Proc. 8th Ann. ACM Symp. on Computational Geometry, pages 138–145, 1992.
M. de Berg and O. Schwarzkopf. Cuttings and applications.Internat. J. Comput. Geom. Appl., 5: 343–355, 1995.
H. Brönnimann, B. Chazelle, and J. Pach. How hard is half-space range searching?Discrete Comput. Geom., 10:143–155, 1993.
B. Chazelle. Reporting and counting segment intersections.J. Comput. System Sci., 32:156–182, 1986.
B. Chazelle. Lower bounds on the complexity of polytope range searching.J. Amer. Math. Soc., 2:637–666, 1989.
B. Chazelle. Cutting hyperplanes for divide-and-conquer.Discrete Comput. Geom., 9:145–158, 1993.
B. Chazelle. Lower bounds for off-line range searching.Proc. 27th Ann. ACM Symp. Theory of Computing, pages 733–740, 1995.
B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Diameter, width, closest line pair, and parametric searching.Discrete Comput. Geom., 10:183–196, 1993.
B. Chazelle and B. Rosenberg. Simplex range reporting on a pointer machine.Comput. Geom. Theory Appl., 5:237–247, 1996.
B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems.Algorithmica, 8:407–429, 1992.
F. R. K. Chung, P. Erdós, and J. Spencer. On the decomposition of graphs into complete bipartite subgraphs. In P. Erdós, editor,Studies in Pure Mathematics, pages 95–101. Birkhäuser, Borel, 1983.
K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arragements of curves and spheres.Discrete Comput. Geom., 5:99–160, 1990.
R. Cole, M. Sharir, and C. K. Yap. Onk-hulls and related problems.SIAM J. Comput., 16:61–77, 1987.
H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, volume 10. Springer-Verlag, New York, 1987.
H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, and E. Welzl. Implicitly representing arrangements of lines or segments.Discrete Comput. Geom., 4:433–466, 1989.
H. Edelsbrunner, L. Guibas, and M. Sharir. The complexity of many cells in arrangements of planes and related problems.Discrete Comput. Geom., 5:197–216, 1990.
H. Edelsbrunner, L. J. Guibas, and M. Sharir. The complexity and construction of many faces in arrangements of lines and of segments.Discrete Comput. Geom., 5:161–196, 1990.
H. Edelsbrunner and M. Sharir. A hyperplane incidence problem with applications to counting distances. In P. Gritzman and B. Sturmfels, editors,Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift, pages 253–263. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 4. American Mathematical Society, Providence, RI, 1991.
P. Erdós. On a set of distances ofn points.Amer. Math. Monthly, 53:248–250, 1946.
J. Erickson. On the relative complexities of some geometric problems.Proc. 7th Canad. Conf. on Computational Geometry, pages 85–90, 1995.
J. Erickson and R. Seidel. Better lower bounds on detecting affine and spherical degeneracies.Proc. 34th Ann. IEEE Symp. on Foundations of Computer Science (FOCS93), pages 528–536, 1993.
M. L. Fredman. Lower bounds on the complexity of some optimal data structures.SIAM J. Comput., 10:1–10, 1981.
G. Hardy and E. Wright.The Theory of Numbers, 4th edition. Oxford University Press, London, 1965.
M. J. Katz and M. Sharir. An expander-based approach to geometric optimization.Proc. 9th Ann. ACM Symp. on Computational Geometry, pages 198–207, 1993.
L. Lovàsz. Communication complexity: A survey. InPaths, Flows, and VLSI Layout, pages 235–265. Algorithms and Combinatorics, volume 9. Springer-Verlag, New York, 1990.
J. Matoušek and O. Schwarzkopf. On ray shooting in convex polytopes.Discrete Comput. Geom., 10: 215–232, 1993.
J. Matoušek. Range searching with efficient hierarchical cuttings.Discrete Comput. Geom., 10:157–182, 1993.
M. Pellegrini. Incidence and nearest-neighbor problems for lines in 3-space.Proc. 8th Ann. ACM Symp. on Computational Geometry, pages 130–137, 1992.
R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons.Comput. Geom. Theory Appl., 1:51–64, 1991.
J. Spencer, E. Szemerédi, and W. T. Trotter, Jr. Unit distances in the Euclidean plane. In B. Bollobás, editor,Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference in Honor of Paul Erdós, pages 293–303. Academic Press, London, 1984.
J. M. Steele and A. C. Yao. Lower bounds for algebraic decision trees.J. Algorithms, 3:1–8, 1982.
J. Stolfi.Oriented Projective Geometry: A Framework for Geometric Computations. Academic Press, New York, 1991.
E. Szemerédi and W. T. Trotter, Jr. Extremal problems in discrete geometry.Combinatorica, 3: 381–392, 1983.
T. G. Tarján. Complexity of lattice-configurations.Studia Sci. Math. Hungar., 10:203–211, 1975.
Zs. Tuza. Covering of graphs by complete bipartite subgraphs; complexity of 0–1 matrices.Combinatorica, 4:111–116, 1984.
Author information
Authors and Affiliations
Additional 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 Informatik, Universität des Saarlandes, Saarbrücken, Germany, November 1994.
Rights and permissions
About this article
Cite this article
Erickson, J. New lower bounds for Hopcroft's problem. Discrete Comput Geom 16, 389–418 (1996). https://doi.org/10.1007/BF02712875
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF02712875