{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,15]],"date-time":"2026-06-15T13:50:26Z","timestamp":1781531426920,"version":"3.54.5"},"reference-count":38,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[1996,4,1]],"date-time":"1996-04-01T00:00:00Z","timestamp":828316800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[1996,4]]},"DOI":"10.1007\/bf02712875","type":"journal-article","created":{"date-parts":[[2007,10,3]],"date-time":"2007-10-03T05:58:49Z","timestamp":1191391129000},"page":"389-418","source":"Crossref","is-referenced-by-count":36,"title":["New lower bounds for Hopcroft's problem"],"prefix":"10.1007","volume":"16","author":[{"given":"J.","family":"Erickson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"BF02712875_CR1","doi-asserted-by":"crossref","first-page":"533","DOI":"10.1007\/BF02187809","volume":"5","author":"P. K. Agarwal","year":"1990","unstructured":"P. K. Agarwal. Partitioning arrangements of lines: II. Applications.Discrete Comput. Geom., 5:533\u2013573, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR2","doi-asserted-by":"crossref","unstructured":"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\u2013347, 1993.","DOI":"10.1145\/160985.161160"},{"key":"BF02712875_CR3","doi-asserted-by":"crossref","unstructured":"M. Ben-Or. Lower bounds for algebraic computation trees.Proc. 15th Ann. ACM Symp. on Theory of Computing, pages 80\u201386, 1983.","DOI":"10.1145\/800061.808735"},{"key":"BF02712875_CR4","doi-asserted-by":"crossref","unstructured":"M. de Berg, M. Overmars, and O. Schwarzkopf. Computing and verifying depth orders.Proc. 8th Ann. ACM Symp. on Computational Geometry, pages 138\u2013145, 1992.","DOI":"10.1145\/142675.142708"},{"key":"BF02712875_CR5","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1142\/S0218195995000210","volume":"5","author":"M. Berg de","year":"1995","unstructured":"M. de Berg and O. Schwarzkopf. Cuttings and applications.Internat. J. Comput. Geom. Appl., 5: 343\u2013355, 1995.","journal-title":"Internat. J. Comput. Geom. Appl."},{"key":"BF02712875_CR6","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF02573971","volume":"10","author":"H. Br\u00f6nnimann","year":"1993","unstructured":"H. Br\u00f6nnimann, B. Chazelle, and J. Pach. How hard is half-space range searching?Discrete Comput. Geom., 10:143\u2013155, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR7","doi-asserted-by":"crossref","first-page":"156","DOI":"10.1016\/0022-0000(86)90025-5","volume":"32","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle. Reporting and counting segment intersections.J. Comput. System Sci., 32:156\u2013182, 1986.","journal-title":"J. Comput. System Sci."},{"key":"BF02712875_CR8","doi-asserted-by":"crossref","first-page":"637","DOI":"10.1090\/S0894-0347-1989-1001852-0","volume":"2","author":"B. Chazelle","year":"1989","unstructured":"B. Chazelle. Lower bounds on the complexity of polytope range searching.J. Amer. Math. Soc., 2:637\u2013666, 1989.","journal-title":"J. Amer. Math. Soc."},{"key":"BF02712875_CR9","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02189314","volume":"9","author":"B. Chazelle","year":"1993","unstructured":"B. Chazelle. Cutting hyperplanes for divide-and-conquer.Discrete Comput. Geom., 9:145\u2013158, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR10","doi-asserted-by":"crossref","unstructured":"B. Chazelle. Lower bounds for off-line range searching.Proc. 27th Ann. ACM Symp. Theory of Computing, pages 733\u2013740, 1995.","DOI":"10.1145\/225058.225291"},{"key":"BF02712875_CR11","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1007\/BF02573973","volume":"10","author":"B. Chazelle","year":"1993","unstructured":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir. Diameter, width, closest line pair, and parametric searching.Discrete Comput. Geom., 10:183\u2013196, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR12","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0925-7721(95)00002-X","volume":"5","author":"B. Chazelle","year":"1996","unstructured":"B. Chazelle and B. Rosenberg. Simplex range reporting on a pointer machine.Comput. Geom. Theory Appl., 5:237\u2013247, 1996.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02712875_CR13","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF01758854","volume":"8","author":"B. Chazelle","year":"1992","unstructured":"B. Chazelle, M. Sharir, and E. Welzl. Quasi-optimal upper bounds for simplex range searching and new zone theorems.Algorithmica, 8:407\u2013429, 1992.","journal-title":"Algorithmica"},{"key":"BF02712875_CR14","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1007\/978-3-0348-5438-2_10","volume-title":"Studies in Pure Mathematics","author":"F. R. K. Chung","year":"1983","unstructured":"F. R. K. Chung, P. Erd\u00f3s, and J. Spencer. On the decomposition of graphs into complete bipartite subgraphs. In P. Erd\u00f3s, editor,Studies in Pure Mathematics, pages 95\u2013101. Birkh\u00e4user, Borel, 1983."},{"key":"BF02712875_CR15","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1007\/BF02187783","volume":"5","author":"K. Clarkson","year":"1990","unstructured":"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\u2013160, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR16","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1137\/0216005","volume":"16","author":"R. Cole","year":"1987","unstructured":"R. Cole, M. Sharir, and C. K. Yap. Onk-hulls and related problems.SIAM J. Comput., 16:61\u201377, 1987.","journal-title":"SIAM J. Comput."},{"key":"BF02712875_CR17","series-title":"EATCS Monographs on Theoretical Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, volume 10. Springer-Verlag, New York, 1987."},{"key":"BF02712875_CR18","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1007\/BF02187742","volume":"4","author":"H. Edelsbrunner","year":"1989","unstructured":"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\u2013466, 1989.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR19","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/BF02187785","volume":"5","author":"H. Edelsbrunner","year":"1990","unstructured":"H. Edelsbrunner, L. Guibas, and M. Sharir. The complexity of many cells in arrangements of planes and related problems.Discrete Comput. Geom., 5:197\u2013216, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR20","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/BF02187784","volume":"5","author":"H. Edelsbrunner","year":"1990","unstructured":"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\u2013196, 1990.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR21","series-title":"DIMACS Series in Discrete Mathematics and Theoretical Computer Science","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1090\/dimacs\/004\/18","volume-title":"Applied Geometry and Discrete Mathematics: The Victor Klee Festschrift","author":"H. Edelsbrunner","year":"1991","unstructured":"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\u2013263. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 4. American Mathematical Society, Providence, RI, 1991."},{"key":"BF02712875_CR22","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1080\/00029890.1946.11991674","volume":"53","author":"P. Erd\u00f3s","year":"1946","unstructured":"P. Erd\u00f3s. On a set of distances ofn points.Amer. Math. Monthly, 53:248\u2013250, 1946.","journal-title":"Amer. Math. Monthly"},{"key":"BF02712875_CR23","unstructured":"J. Erickson. On the relative complexities of some geometric problems.Proc. 7th Canad. Conf. on Computational Geometry, pages 85\u201390, 1995."},{"key":"BF02712875_CR24","doi-asserted-by":"crossref","unstructured":"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\u2013536, 1993.","DOI":"10.1109\/SFCS.1993.366834"},{"key":"BF02712875_CR25","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1137\/0210001","volume":"10","author":"M. L. Fredman","year":"1981","unstructured":"M. L. Fredman. Lower bounds on the complexity of some optimal data structures.SIAM J. Comput., 10:1\u201310, 1981.","journal-title":"SIAM J. Comput."},{"key":"BF02712875_CR26","volume-title":"The Theory of Numbers","author":"G. Hardy","year":"1965","unstructured":"G. Hardy and E. Wright.The Theory of Numbers, 4th edition. Oxford University Press, London, 1965.","edition":"4th edition"},{"key":"BF02712875_CR27","doi-asserted-by":"crossref","unstructured":"M. J. Katz and M. Sharir. An expander-based approach to geometric optimization.Proc. 9th Ann. ACM Symp. on Computational Geometry, pages 198\u2013207, 1993.","DOI":"10.1145\/160985.161137"},{"key":"BF02712875_CR28","series-title":"Algorithms and Combinatorics","first-page":"235","volume-title":"Paths, Flows, and VLSI Layout","author":"L. Lov\u00e0sz","year":"1990","unstructured":"L. Lov\u00e0sz. Communication complexity: A survey. InPaths, Flows, and VLSI Layout, pages 235\u2013265. Algorithms and Combinatorics, volume 9. Springer-Verlag, New York, 1990."},{"key":"BF02712875_CR29","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1007\/BF02573975","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek and O. Schwarzkopf. On ray shooting in convex polytopes.Discrete Comput. Geom., 10: 215\u2013232, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR30","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF02573972","volume":"10","author":"J. Matou\u0161ek","year":"1993","unstructured":"J. Matou\u0161ek. Range searching with efficient hierarchical cuttings.Discrete Comput. Geom., 10:157\u2013182, 1993.","journal-title":"Discrete Comput. Geom."},{"key":"BF02712875_CR31","doi-asserted-by":"crossref","unstructured":"M. Pellegrini. Incidence and nearest-neighbor problems for lines in 3-space.Proc. 8th Ann. ACM Symp. on Computational Geometry, pages 130\u2013137, 1992.","DOI":"10.1145\/142675.142703"},{"key":"BF02712875_CR32","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/0925-7721(91)90012-4","volume":"1","author":"R. Seidel","year":"1991","unstructured":"R. Seidel. A simple and fast incremental randomized algorithm for computing trapezoidal decompositions and for triangulating polygons.Comput. Geom. Theory Appl., 1:51\u201364, 1991.","journal-title":"Comput. Geom. Theory Appl."},{"key":"BF02712875_CR33","first-page":"293","volume-title":"Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference in Honor of Paul Erd\u00f3s","author":"J. Spencer","year":"1984","unstructured":"J. Spencer, E. Szemer\u00e9di, and W. T. Trotter, Jr. Unit distances in the Euclidean plane. In B. Bollob\u00e1s, editor,Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatorial Conference in Honor of Paul Erd\u00f3s, pages 293\u2013303. Academic Press, London, 1984."},{"key":"BF02712875_CR34","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0196-6774(82)90002-5","volume":"3","author":"J. M. Steele","year":"1982","unstructured":"J. M. Steele and A. C. Yao. Lower bounds for algebraic decision trees.J. Algorithms, 3:1\u20138, 1982.","journal-title":"J. Algorithms"},{"key":"BF02712875_CR35","volume-title":"Oriented Projective Geometry: A Framework for Geometric Computations","author":"J. Stolfi","year":"1991","unstructured":"J. Stolfi.Oriented Projective Geometry: A Framework for Geometric Computations. Academic Press, New York, 1991."},{"key":"BF02712875_CR36","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1007\/BF02579194","volume":"3","author":"E. Szemer\u00e9di","year":"1983","unstructured":"E. Szemer\u00e9di and W. T. Trotter, Jr. Extremal problems in discrete geometry.Combinatorica, 3: 381\u2013392, 1983.","journal-title":"Combinatorica"},{"key":"BF02712875_CR37","first-page":"203","volume":"10","author":"T. G. Tarj\u00e1n","year":"1975","unstructured":"T. G. Tarj\u00e1n. Complexity of lattice-configurations.Studia Sci. Math. Hungar., 10:203\u2013211, 1975.","journal-title":"Studia Sci. Math. Hungar."},{"key":"BF02712875_CR38","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1007\/BF02579163","volume":"4","author":"Zs. Tuza","year":"1984","unstructured":"Zs. Tuza. Covering of graphs by complete bipartite subgraphs; complexity of 0\u20131 matrices.Combinatorica, 4:111\u2013116, 1984.","journal-title":"Combinatorica"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02712875.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02712875\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02712875","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T01:01:23Z","timestamp":1558227683000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02712875"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1996,4]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1996,4]]}},"alternative-id":["BF02712875"],"URL":"https:\/\/doi.org\/10.1007\/bf02712875","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1996,4]]}}}