[{"language":[{"iso":"eng"}],"oa_version":"Published Version","month":"12","publication":"Discrete & Computational Geometry","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187742","open_access":"1"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"oa":1,"publist_id":"2036","date_published":"1989-12-01T00:00:00Z","type":"journal_article","publisher":"Springer","article_type":"original","page":"433 - 466","quality_controlled":"1","publication_status":"published","date_created":"2018-12-11T12:06:52Z","article_processing_charge":"No","title":"Implicitly representing arrangements of lines or segments","intvolume":"         4","_id":"4088","scopus_import":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"full_name":"Hershberger, John","last_name":"Hershberger","first_name":"John"},{"full_name":"Seidel, Raimund","first_name":"Raimund","last_name":"Seidel"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"full_name":"Snoeyink, Jack","last_name":"Snoeyink","first_name":"Jack"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"issue":"1","acknowledgement":"The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fifth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. The sixth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the non-DEC authors were visiting at the DEC Systems Research Center.","volume":4,"extern":"1","doi":"10.1007/BF02187742","day":"01","abstract":[{"text":"Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.","lang":"eng"}],"date_updated":"2022-02-10T15:03:48Z","citation":{"apa":"Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., &#38; Welzl, E. (1989). Implicitly representing arrangements of lines or segments. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187742\">https://doi.org/10.1007/BF02187742</a>","ama":"Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements of lines or segments. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):433-466. doi:<a href=\"https://doi.org/10.1007/BF02187742\">10.1007/BF02187742</a>","ieee":"H. Edelsbrunner <i>et al.</i>, “Implicitly representing arrangements of lines or segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 433–466, 1989.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187742\">https://doi.org/10.1007/BF02187742</a>.","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl, Discrete &#38; Computational Geometry 4 (1989) 433–466.","mla":"Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 433–66, doi:<a href=\"https://doi.org/10.1007/BF02187742\">10.1007/BF02187742</a>.","ista":"Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M, Snoeyink J, Welzl E. 1989. Implicitly representing arrangements of lines or segments. Discrete &#38; Computational Geometry. 4(1), 433–466."},"year":"1989"},{"publication":"Discrete & Computational Geometry","oa_version":"Published Version","month":"12","language":[{"iso":"eng"}],"type":"journal_article","date_published":"1989-12-01T00:00:00Z","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publist_id":"2037","oa":1,"main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187745"}],"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","scopus_import":"1","_id":"4089","issue":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"full_name":"Hershberger, John","last_name":"Hershberger","first_name":"John"},{"first_name":"János","last_name":"Pach","full_name":"Pach, János"},{"last_name":"Pollack","first_name":"Richard","full_name":"Pollack, Richard"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"first_name":"Jack","last_name":"Snoeyink","full_name":"Snoeyink, Jack"}],"date_created":"2018-12-11T12:06:52Z","article_processing_charge":"No","publication_status":"published","intvolume":"         4","title":"On arrangements of Jordan arcs with three intersections per pair","quality_controlled":"1","page":"523 - 539","publisher":"Springer","article_type":"original","year":"1989","citation":{"chicago":"Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187745\">https://doi.org/10.1007/BF02187745</a>.","ieee":"H. Edelsbrunner <i>et al.</i>, “On arrangements of Jordan arcs with three intersections per pair,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 523–539, 1989.","ama":"Edelsbrunner H, Guibas L, Hershberger J, et al. On arrangements of Jordan arcs with three intersections per pair. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):523-539. doi:<a href=\"https://doi.org/10.1007/BF02187745\">10.1007/BF02187745</a>","apa":"Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel, R., … Snoeyink, J. (1989). On arrangements of Jordan arcs with three intersections per pair. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187745\">https://doi.org/10.1007/BF02187745</a>","ista":"Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per pair. Discrete &#38; Computational Geometry. 4(1), 523–539.","mla":"Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 523–39, doi:<a href=\"https://doi.org/10.1007/BF02187745\">10.1007/BF02187745</a>.","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, Discrete &#38; Computational Geometry 4 (1989) 523–539."},"date_updated":"2022-02-10T15:40:04Z","day":"01","doi":"10.1007/BF02187745","abstract":[{"text":"Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function.","lang":"eng"}],"acknowledgement":"The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fourth and seventh authors has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. The seventh author in addition wishes to acknowledge support by a research grant from the NCRD—the Israeli National Council for Research and Development. The fifth author would like to acknowledge support in part by NSF grant DMS-8501947. Finally, the eighth author was supported in part by a National Science Foundation Graduate Fellowship.","volume":4,"extern":"1"},{"page":"139 - 181","quality_controlled":"1","publisher":"Springer","author":[{"last_name":"Chazelle","first_name":"Bernard","full_name":"Chazelle, Bernard"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"}],"issue":"1","_id":"4093","title":"The complexity of cutting complexes","intvolume":"         4","publication_status":"published","date_created":"2018-12-11T12:06:54Z","article_processing_charge":"No","extern":"1","volume":4,"acknowledgement":"Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant No. MCS83-03925. Herbert Edelsbrunner is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. We wish to thank J. Pach and E. Szemeredi for valuable discussions on several\r\nof the problems studied in this paper.","date_updated":"2022-02-10T10:25:57Z","citation":{"apa":"Chazelle, B., Edelsbrunner, H., &#38; Guibas, L. (1989). The complexity of cutting complexes. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187720\">https://doi.org/10.1007/BF02187720</a>","ama":"Chazelle B, Edelsbrunner H, Guibas L. The complexity of cutting complexes. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):139-181. doi:<a href=\"https://doi.org/10.1007/BF02187720\">10.1007/BF02187720</a>","ieee":"B. Chazelle, H. Edelsbrunner, and L. Guibas, “The complexity of cutting complexes,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 139–181, 1989.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, and Leonidas Guibas. “The Complexity of Cutting Complexes.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187720\">https://doi.org/10.1007/BF02187720</a>.","mla":"Chazelle, Bernard, et al. “The Complexity of Cutting Complexes.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 139–81, doi:<a href=\"https://doi.org/10.1007/BF02187720\">10.1007/BF02187720</a>.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, Discrete &#38; Computational Geometry 4 (1989) 139–181.","ista":"Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes. Discrete &#38; Computational Geometry. 4(1), 139–181."},"year":"1989","abstract":[{"text":"This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.","lang":"eng"}],"doi":"10.1007/BF02187720","day":"01","language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","month":"03","oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187720"}],"date_published":"1989-03-01T00:00:00Z","type":"journal_article","publist_id":"2032","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]}},{"status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","date_published":"1987-01-01T00:00:00Z","type":"journal_article","publist_id":"2022","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"language":[{"iso":"eng"}],"publication":"Discrete & Computational Geometry","month":"01","oa_version":"None","extern":"1","volume":2,"acknowledgement":"This research was conducted while the first author was with Brown University and the second author was with the Technical University of Graz, Austria. The first author was supported in part by NSF Grant MCS 83-03925.","date_updated":"2022-02-03T11:07:26Z","year":"1987","citation":{"mla":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>, vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:<a href=\"https://doi.org/10.1007/BF02187875\">10.1007/BF02187875</a>.","short":"B. Chazelle, H. Edelsbrunner, Discrete &#38; Computational Geometry 2 (1987) 113–126.","ista":"Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types of range search. Discrete &#38; Computational Geometry. 2(1), 113–126.","apa":"Chazelle, B., &#38; Edelsbrunner, H. (1987). Linear space data structures for two types of range search. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187875\">https://doi.org/10.1007/BF02187875</a>","ama":"Chazelle B, Edelsbrunner H. Linear space data structures for two types of range search. <i>Discrete &#38; Computational Geometry</i>. 1987;2(1):113-126. doi:<a href=\"https://doi.org/10.1007/BF02187875\">10.1007/BF02187875</a>","chicago":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1987. <a href=\"https://doi.org/10.1007/BF02187875\">https://doi.org/10.1007/BF02187875</a>.","ieee":"B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types of range search,” <i>Discrete &#38; Computational Geometry</i>, vol. 2, no. 1. Springer, pp. 113–126, 1987."},"abstract":[{"text":"This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE 3 and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.\r\n","lang":"eng"}],"doi":"10.1007/BF02187875","day":"01","page":"113 - 126","quality_controlled":"1","article_type":"original","publisher":"Springer","author":[{"full_name":"Chazelle, Bernard","first_name":"Bernard","last_name":"Chazelle"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"}],"issue":"1","_id":"4100","scopus_import":"1","title":"Linear space data structures for two types of range search","intvolume":"         2","publication_status":"published","article_processing_charge":"No","date_created":"2018-12-11T12:06:56Z"},{"year":"1986","citation":{"short":"H. Edelsbrunner, R. Seidel, Discrete &#38; Computational Geometry 1 (1986) 25–44.","mla":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” <i>Discrete &#38; Computational Geometry</i>, vol. 1, no. 1, Springer, 1986, pp. 25–44, doi:<a href=\"https://doi.org/10.1007/BF02187681\">10.1007/BF02187681</a>.","ista":"Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete &#38; Computational Geometry. 1(1), 25–44.","apa":"Edelsbrunner, H., &#38; Seidel, R. (1986). Voronoi diagrams and arrangements. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187681\">https://doi.org/10.1007/BF02187681</a>","ama":"Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. <i>Discrete &#38; Computational Geometry</i>. 1986;1(1):25-44. doi:<a href=\"https://doi.org/10.1007/BF02187681\">10.1007/BF02187681</a>","ieee":"H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” <i>Discrete &#38; Computational Geometry</i>, vol. 1, no. 1. Springer, pp. 25–44, 1986.","chicago":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1986. <a href=\"https://doi.org/10.1007/BF02187681\">https://doi.org/10.1007/BF02187681</a>."},"date_updated":"2022-02-01T08:53:39Z","day":"01","doi":"10.1007/BF02187681","abstract":[{"lang":"eng","text":"We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems."}],"acknowledgement":"We would like to thank John Gilbert for his careful reading of the manuscript and his many suggestions for improvement. We also want to thank Bennett Battaile, Gianfranco Bilardi, Joseph O'Rourke, and Chee Yap for their comments. ","volume":1,"extern":"1","_id":"4108","issue":"1","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"first_name":"Raimund","last_name":"Seidel","full_name":"Seidel, Raimund"}],"date_created":"2018-12-11T12:06:59Z","article_processing_charge":"No","publication_status":"published","intvolume":"         1","title":"Voronoi diagrams and arrangements","quality_controlled":"1","page":"25 - 44","publisher":"Springer","article_type":"original","type":"journal_article","date_published":"1986-01-01T00:00:00Z","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publist_id":"2012","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication":"Discrete & Computational Geometry","oa_version":"None","month":"01","language":[{"iso":"eng"}]}]