{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T17:19:02Z","timestamp":1787505542494,"version":"build-2736575974"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[1989,10,1]],"date-time":"1989-10-01T00:00:00Z","timestamp":623203200000},"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":[[1989,10]]},"DOI":"10.1007\/bf02187742","type":"journal-article","created":{"date-parts":[[2005,9,20]],"date-time":"2005-09-20T14:57:34Z","timestamp":1127228254000},"page":"433-466","source":"Crossref","is-referenced-by-count":35,"title":["Implicitly representing arrangements of lines or segments"],"prefix":"10.1007","volume":"4","author":[{"given":"Herbert","family":"Edelsbrunner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leonidas","family":"Guibas","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Hershberger","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raimund","family":"Seidel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Micha","family":"Sharir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jack","family":"Snoeyink","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Emo","family":"Welzl","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[1989,10,1]]},"reference":[{"key":"BF02187742_CR1","doi-asserted-by":"crossref","unstructured":"B. Aronov and M. Sharir. Triangles in space, or building and analyzing castles in the air. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 381\u2013391, ACM, June 1988.","DOI":"10.1145\/73393.73432"},{"issue":"9","key":"BF02187742_CR2","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1109\/TC.1979.1675432","volume":"28","author":"J. L. Bentley","year":"1979","unstructured":"J. L. Bentley and T. A. Ottman. Algorithms for reporting and counting geometric intersections.IEEE Transactions on Computers, 28(9):643\u2013647, 1979.","journal-title":"IEEE Transactions on Computers"},{"key":"BF02187742_CR3","unstructured":"K. Q. Brown. Geometric Transforms for Fast Geometric Algorithms. Ph.D. thesis, Carnegie-Mellon University, 1980."},{"key":"BF02187742_CR4","doi-asserted-by":"crossref","unstructured":"B. Chazelle and H. Edelsbrunner. An optimal algorithm for intersecting line segments in the plane. InProceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 590\u2013600, IEEE, 1988.","DOI":"10.1109\/SFCS.1988.21975"},{"key":"BF02187742_CR5","doi-asserted-by":"crossref","unstructured":"B. Chazelle and L. Guibas. Visibility and intersection problems in plane geometry. InProceedings of the ACM Symposium on Computational Geometry, pages 135\u2013146, ACM, 1985. Submitted toDiscrete and Computational Geometry.","DOI":"10.1145\/323233.323252"},{"key":"BF02187742_CR6","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/BF01840441","volume":"1","author":"B. Chazelle","year":"1986","unstructured":"B. Chazelle and L. J. Guibas. Fractional cascading: II. Applications.Algorithmica, 1:163\u2013191, 1986.","journal-title":"Algorithmica"},{"key":"BF02187742_CR7","doi-asserted-by":"crossref","first-page":"76","DOI":"10.1007\/BF01934990","volume":"25","author":"B. Chazelle","year":"1985","unstructured":"B. Chazelle, L. J. Guibas, and D. T. Lee. The power of geometric duality.BIT, 25:76\u201390, 1985.","journal-title":"BIT"},{"key":"BF02187742_CR8","unstructured":"B. Chazelle and E. Welzl. Range searching and VC-dimension: a characterization of efficiency. 1988. Manuscript."},{"key":"BF02187742_CR9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/BF02187879","volume":"2","author":"K. Clarkson","year":"1987","unstructured":"K. Clarkson. New applications of random sampling in computational geometry.Discrete and Computational Geometry, 2:195\u2013222, 1987.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02187742_CR10","doi-asserted-by":"crossref","unstructured":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl. Combinatorial complexity bounds for arrangements of curves and surfaces. InProceedings of the 29th Annual IEEE Symposium on Foundations of Computer Science, pages 568\u2013579, IEEE, 1988.","DOI":"10.1109\/SFCS.1988.21973"},{"key":"BF02187742_CR11","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-61568-9","volume-title":"Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, Volume 10","author":"H. Edelsbrunner","year":"1987","unstructured":"H. Edelsbrunner.Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, Volume 10, Springer-Verlag, Berlin, 1987."},{"key":"BF02187742_CR12","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner and L. J. Guibas. Topologically sweeping an arrangement. InProceedings of the 18th ACM Symposium on Theory of Computing, pages 389\u2013403, ACM, May 1986.","DOI":"10.1145\/12130.12171"},{"key":"BF02187742_CR13","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, L. Guibas, J. Pach, R. Pollack, R. Seidel, and M. Sharir. Arrangements of curves in the plane: Topology, combinatorics, and algorithms. InProceedings of the 15th ICALP, 1988.","DOI":"10.1007\/3-540-19488-6_118"},{"key":"BF02187742_CR14","doi-asserted-by":"crossref","unstructured":"H. Edelsbrunner, L. J. Guibas, and M. Sharir. The complexity of many faces in arrangements of lines and of segments. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 44\u201355, ACM, June 1988.","DOI":"10.1145\/73393.73399"},{"key":"BF02187742_CR15","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1137\/0215023","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, L. Guibas, and J. Stolfi. Optimal point location in a monotone subdivision.SIAM Journal on Computing, 15:317\u2013340, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"BF02187742_CR16","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1137\/0215024","volume":"15","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner, J. O'Rourke, and R. Seidel. Constructing arrangements of lines and hyperplanes with applications.SIAM Journal on Computing, 15:341\u2013363, 1986.","journal-title":"SIAM Journal on Computing"},{"key":"BF02187742_CR17","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0020-0190(86)90088-8","volume":"23","author":"H. Edelsbrunner","year":"1986","unstructured":"H. Edelsbrunner and E. Welzl. Halfplanar range search in linear space andO(n 0 695) query time.Information Processing Letters, 23:289\u2013293, 1986.","journal-title":"Information Processing Letters"},{"key":"BF02187742_CR18","doi-asserted-by":"crossref","unstructured":"L. Guibas and J. Hershberger. Optimal shortest path queries in a simple polygon. InProceedings of the 3rd ACM Symposium on Computational Geometry, pages 50\u201363, ACM, June 1987.","DOI":"10.1145\/41958.41964"},{"key":"BF02187742_CR19","unstructured":"L. Guibas, J. Hershberger, and J. Snoeyink. Bridge trees: a data structure for convex hulls. 1989. In preparation."},{"key":"BF02187742_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"64","DOI":"10.1007\/3-540-19487-8_7","volume-title":"Proceedings of the First Scandinavian Workshop on Algorithm Theory","author":"L. Guibas","year":"1988","unstructured":"L. Guibas, M. Overmars, and M. Sharir. Interesting line segments, ray shooting, and other applications of geometric partitioning techniques. InProceedings of the First Scandinavian Workshop on Algorithm Theory, pages 64\u201373. Lecture Notes in Computer Science, Volume 318, Springer-Verlag, Berlin, 1988."},{"key":"BF02187742_CR21","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"D. Haussler and E. Welzl. Epsilon-nets and simplex range queries.Discrete and Computational Geometry, 2:127\u2013151, 1987.","journal-title":"Discrete and Computational Geometry"},{"key":"BF02187742_CR22","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1137\/0212002","volume":"12","author":"D. Kirkpatrick","year":"1983","unstructured":"D. Kirkpatrick. Optimal search in planar subdivisions.SIAM Journal on Computing, 12:28\u201335, 1983.","journal-title":"SIAM Journal on Computing"},{"key":"BF02187742_CR23","volume-title":"Sorting and Searching. The Art of Computer Programming, Volume 3","author":"D. E. Knuth","year":"1973","unstructured":"D. E. Knuth.Sorting and Searching. The Art of Computer Programming, Volume 3, Addison-Wesley, Reading, MA, 1973."},{"key":"BF02187742_CR24","unstructured":"J. Matou\u0161ek. Spanning trees with low crossing number. 1988. Manuscript."},{"key":"BF02187742_CR25","doi-asserted-by":"crossref","first-page":"166","DOI":"10.1016\/0022-0000(81)90012-X","volume":"23","author":"M. Overmars","year":"1981","unstructured":"M. Overmars and H. van Leeuwen. Maintenance of configurations in the plane.Journal of Computer and System Sciences, 23:166\u2013204, 1981.","journal-title":"Journal of Computer and System Sciences"},{"key":"BF02187742_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"F. P. Preparata and M. I. Shamos.Computational Geometry. Springer-Verlag, New York, 1985."},{"key":"BF02187742_CR27","doi-asserted-by":"crossref","first-page":"669","DOI":"10.1145\/6138.6151","volume":"29","author":"N. Sarnak","year":"1986","unstructured":"N. Sarnak and R. E. Tarjan. Planar point location using persistent search trees.Communications of the ACM, 29:669\u2013679, 1986.","journal-title":"Communications of the ACM"},{"key":"BF02187742_CR28","doi-asserted-by":"crossref","unstructured":"M. I. Shamos and D. Hoey. Geometric intersection problems. InProceedings of the 17th IEEE Symposium on Foundations of Computer Science, pages 208\u2013215, IEEE, 1976.","DOI":"10.1109\/SFCS.1976.16"},{"key":"BF02187742_CR29","doi-asserted-by":"crossref","unstructured":"E. Welzl. Partition trees for triangle counting and other range searching problems. InProceedings of the 4th ACM Symposium on Computational Geometry, pages 23\u201333, ACM, June 1988.","DOI":"10.1145\/73393.73397"},{"key":"BF02187742_CR30","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1137\/0211012","volume":"11","author":"D. E. Willard","year":"1982","unstructured":"D. E. Willard. Polygon retrieval.SIAM Journal on Computing, 11:149\u2013165, 1982.","journal-title":"SIAM Journal on Computing"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187742.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF02187742\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF02187742","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,9]],"date-time":"2020-04-09T13:58:27Z","timestamp":1586440707000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF02187742"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1989,10]]},"references-count":30,"journal-issue":{"issue":"5","published-print":{"date-parts":[[1989,10]]}},"alternative-id":["BF02187742"],"URL":"https:\/\/doi.org\/10.1007\/bf02187742","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[1989,10]]}}}