[{"publist_id":"2080","date_created":"2018-12-11T12:06:38Z","citation":{"chicago":"Aggarwal, Alok, Herbert Edelsbrunner, Prabhakar Raghavan, and Prasoon Tiwari. “Optimal Time Bounds for Some Proximity Problems in the Plane.” <i>Information Processing Letters</i>. Elsevier, 1992. <a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">https://doi.org/10.1016/0020-0190(92)90133-G</a>.","ista":"Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. 1992. Optimal time bounds for some proximity problems in the plane. Information Processing Letters. 42(1), 55–60.","mla":"Aggarwal, Alok, et al. “Optimal Time Bounds for Some Proximity Problems in the Plane.” <i>Information Processing Letters</i>, vol. 42, no. 1, Elsevier, 1992, pp. 55–60, doi:<a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">10.1016/0020-0190(92)90133-G</a>.","ama":"Aggarwal A, Edelsbrunner H, Raghavan P, Tiwari P. Optimal time bounds for some proximity problems in the plane. <i>Information Processing Letters</i>. 1992;42(1):55-60. doi:<a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">10.1016/0020-0190(92)90133-G</a>","ieee":"A. Aggarwal, H. Edelsbrunner, P. Raghavan, and P. Tiwari, “Optimal time bounds for some proximity problems in the plane,” <i>Information Processing Letters</i>, vol. 42, no. 1. Elsevier, pp. 55–60, 1992.","short":"A. Aggarwal, H. Edelsbrunner, P. Raghavan, P. Tiwari, Information Processing Letters 42 (1992) 55–60.","apa":"Aggarwal, A., Edelsbrunner, H., Raghavan, P., &#38; Tiwari, P. (1992). Optimal time bounds for some proximity problems in the plane. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(92)90133-G\">https://doi.org/10.1016/0020-0190(92)90133-G</a>"},"acknowledgement":"Research supported by the National Science Foundation under Grant CCR-8714565.","year":"1992","_id":"4048","article_type":"original","doi":"10.1016/0020-0190(92)90133-G","publication_status":"published","abstract":[{"lang":"eng","text":"Given a sequence of n points that form the vertices of a simple polygon, we show that determining a closest pair requires OMEGA(n log n) time in the algebraic decision tree model. Together with the well-known O(n log n) upper bound for finding a closest pair, this settles an open problem of Lee and Preparata. We also extend this O(n log n) upper bound to the following problem: Given a collection of sets with a total of n points in the plane, find for each point a closest neighbor that does not belong to the same set."}],"page":"55 - 60","extern":"1","quality_controlled":"1","volume":42,"publisher":"Elsevier","date_published":"1992-04-27T00:00:00Z","title":"Optimal time bounds for some proximity problems in the plane","date_updated":"2022-03-16T09:20:13Z","article_processing_charge":"No","issue":"1","scopus_import":"1","intvolume":"        42","language":[{"iso":"eng"}],"publication":"Information Processing Letters","author":[{"last_name":"Aggarwal","full_name":"Aggarwal, Alok","first_name":"Alok"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"first_name":"Prabhakar","full_name":"Raghavan, Prabhakar","last_name":"Raghavan"},{"full_name":"Tiwari, Prasoon","first_name":"Prasoon","last_name":"Tiwari"}],"main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/002001909290133G"}],"day":"27","oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"eissn":["1872-6119"],"issn":["0020-0190"]},"month":"04","type":"journal_article","status":"public"},{"page":"61 - 64","extern":"1","quality_controlled":"1","volume":26,"publisher":"Elsevier","date_published":"1987-10-19T00:00:00Z","publication_status":"published","abstract":[{"lang":"eng","text":"The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight."}],"_id":"4094","article_type":"original","doi":"10.1016/0020-0190(87)90038-X","citation":{"apa":"Edelsbrunner, H., &#38; Shen, X. (1987). A tight lower bound on the size of visibility graphs. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">https://doi.org/10.1016/0020-0190(87)90038-X</a>","ieee":"H. Edelsbrunner and X. Shen, “A tight lower bound on the size of visibility graphs,” <i>Information Processing Letters</i>, vol. 26, no. 2. Elsevier, pp. 61–64, 1987.","ama":"Edelsbrunner H, Shen X. A tight lower bound on the size of visibility graphs. <i>Information Processing Letters</i>. 1987;26(2):61-64. doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">10.1016/0020-0190(87)90038-X</a>","short":"H. Edelsbrunner, X. Shen, Information Processing Letters 26 (1987) 61–64.","mla":"Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size of Visibility Graphs.” <i>Information Processing Letters</i>, vol. 26, no. 2, Elsevier, 1987, pp. 61–64, doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">10.1016/0020-0190(87)90038-X</a>.","chicago":"Edelsbrunner, Herbert, and Xiaojun Shen. “A Tight Lower Bound on the Size of Visibility Graphs.” <i>Information Processing Letters</i>. Elsevier, 1987. <a href=\"https://doi.org/10.1016/0020-0190(87)90038-X\">https://doi.org/10.1016/0020-0190(87)90038-X</a>.","ista":"Edelsbrunner H, Shen X. 1987. A tight lower bound on the size of visibility graphs. Information Processing Letters. 26(2), 61–64."},"date_created":"2018-12-11T12:06:54Z","publist_id":"2025","acknowledgement":"Research of this author ‘was supported by the Amoco Foundation for Facilitation of Development of Computer\r\nScience under Grant No. l-6-44862.","year":"1987","status":"public","type":"journal_article","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"last_name":"Shen","full_name":"Shen, Xiaojun","first_name":"Xiaojun"}],"oa_version":"None","day":"19","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/002001908790038X?via%3Dihub"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","month":"10","publication_identifier":{"eissn":["1872-6119"],"issn":["0020-0190"]},"language":[{"iso":"eng"}],"publication":"Information Processing Letters","title":"A tight lower bound on the size of visibility graphs","date_updated":"2022-02-03T14:05:19Z","article_processing_charge":"No","issue":"2","scopus_import":"1","intvolume":"        26"},{"date_created":"2018-12-11T12:06:57Z","citation":{"apa":"Edelsbrunner, H., &#38; Overmars, M. (1987). Zooming by repeated range detection. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">https://doi.org/10.1016/0020-0190(87)90120-7</a>","mla":"Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.” <i>Information Processing Letters</i>, vol. 24, no. 6, Elsevier, 1987, pp. 413–17, doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">10.1016/0020-0190(87)90120-7</a>.","ista":"Edelsbrunner H, Overmars M. 1987. Zooming by repeated range detection. Information Processing Letters. 24(6), 413–417.","chicago":"Edelsbrunner, Herbert, and Mark Overmars. “Zooming by Repeated Range Detection.” <i>Information Processing Letters</i>. Elsevier, 1987. <a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">https://doi.org/10.1016/0020-0190(87)90120-7</a>.","short":"H. Edelsbrunner, M. Overmars, Information Processing Letters 24 (1987) 413–417.","ama":"Edelsbrunner H, Overmars M. Zooming by repeated range detection. <i>Information Processing Letters</i>. 1987;24(6):413-417. doi:<a href=\"https://doi.org/10.1016/0020-0190(87)90120-7\">10.1016/0020-0190(87)90120-7</a>","ieee":"H. Edelsbrunner and M. Overmars, “Zooming by repeated range detection,” <i>Information Processing Letters</i>, vol. 24, no. 6. Elsevier, pp. 413–417, 1987."},"publist_id":"2023","year":"1987","doi":"10.1016/0020-0190(87)90120-7","_id":"4101","article_type":"original","abstract":[{"lang":"eng","text":"In a number of recent papers, techniques from computational geometry (the field of algorithm design that deals with objects in multi-dimensional space) have been applied to some problems in the area of computer graphics. In this way, efficient solutions were obtained for the windowing problem that asks for those line segments in a planar set that lie in given window (range) and the moving problem that asks for the first line segment that comes into the window when moving the window in some direction. In this paper we show that also the zooming problem, which asks for the first line segment that comes into the window when we enlarge it, can be solved efficiently. This is done by repeatedly performing range queries with ranges of varying sizes. The obtained structure is dynamic and yields a query time of O(log2n) and an insertion and deletion time of O(log2n), where n is the number of line segments in the set. The amount of storage required is O(n log n). It is also shown that the technique of repeated range search can be used to solve several other problems efficiently."}],"publication_status":"published","volume":24,"quality_controlled":"1","page":"413 - 417","extern":"1","date_published":"1987-04-06T00:00:00Z","publisher":"Elsevier","intvolume":"        24","scopus_import":"1","title":"Zooming by repeated range detection","article_processing_charge":"No","issue":"6","date_updated":"2022-02-03T13:29:17Z","publication":"Information Processing Letters","language":[{"iso":"eng"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","day":"06","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0020019087901207?via%3Dihub"}],"oa_version":"None","publication_identifier":{"eissn":["1872-6119"],"issn":["0020-0190"]},"month":"04","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"last_name":"Overmars","full_name":"Overmars, Mark","first_name":"Mark"}],"status":"public","type":"journal_article"},{"type":"journal_article","status":"public","author":[{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"last_name":"Welzl","full_name":"Welzl, Emo","first_name":"Emo"}],"month":"11","publication_identifier":{"issn":["0020-0190"],"eissn":["1872-6119"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","day":"24","language":[{"iso":"eng"}],"publication":"Information Processing Letters","issue":"5","article_processing_charge":"No","date_updated":"2022-02-01T14:17:10Z","title":"Halfplanar range search in linear space and O(n0.695) query time","intvolume":"        23","date_published":"1986-11-24T00:00:00Z","publisher":"Elsevier","volume":23,"quality_controlled":"1","page":"289 - 293","extern":"1","publication_status":"published","abstract":[{"text":"Let S denote a set of n points in the Euclidean plane. A halfplanar range query specifies a halfplane h and requires the determination of the number of points in S which are contained in h. A new data structure is described which stores S in O(n) space and allows us to answer a halfplanar range query in O(nlog2(1+√5)−1) time in the worst case, thus improving the best result known before. The structure can be built in O(n log n) time.","lang":"eng"}],"article_type":"original","_id":"4099","doi":"10.1016/0020-0190(86)90088-8","year":"1986","acknowledgement":"We thank W. Bucher for help in the analysis of the time complexity of the query algorithm. ","publist_id":"2021","date_created":"2018-12-11T12:06:56Z","citation":{"apa":"Edelsbrunner, H., &#38; Welzl, E. (1986). Halfplanar range search in linear space and O(n0.695) query time. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">https://doi.org/10.1016/0020-0190(86)90088-8</a>","short":"H. Edelsbrunner, E. Welzl, Information Processing Letters 23 (1986) 289–293.","ama":"Edelsbrunner H, Welzl E. Halfplanar range search in linear space and O(n0.695) query time. <i>Information Processing Letters</i>. 1986;23(5):289-293. doi:<a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">10.1016/0020-0190(86)90088-8</a>","ieee":"H. Edelsbrunner and E. Welzl, “Halfplanar range search in linear space and O(n0.695) query time,” <i>Information Processing Letters</i>, vol. 23, no. 5. Elsevier, pp. 289–293, 1986.","mla":"Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space and O(N0.695) Query Time.” <i>Information Processing Letters</i>, vol. 23, no. 5, Elsevier, 1986, pp. 289–93, doi:<a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">10.1016/0020-0190(86)90088-8</a>.","ista":"Edelsbrunner H, Welzl E. 1986. Halfplanar range search in linear space and O(n0.695) query time. Information Processing Letters. 23(5), 289–293.","chicago":"Edelsbrunner, Herbert, and Emo Welzl. “Halfplanar Range Search in Linear Space and O(N0.695) Query Time.” <i>Information Processing Letters</i>. Elsevier, 1986. <a href=\"https://doi.org/10.1016/0020-0190(86)90088-8\">https://doi.org/10.1016/0020-0190(86)90088-8</a>."}},{"doi":"10.1016/0020-0190(85)90107-3","_id":"4111","article_type":"original","citation":{"short":"H. Edelsbrunner, H. Maurer, Information Processing Letters 21 (1985) 39–47.","ieee":"H. Edelsbrunner and H. Maurer, “Finding extreme-points in 3-dimensions and solving the post-office problem in the plane,” <i>Information Processing Letters</i>, vol. 21, no. 1. Elsevier, pp. 39–47, 1985.","ama":"Edelsbrunner H, Maurer H. Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. <i>Information Processing Letters</i>. 1985;21(1):39-47. doi:<a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">10.1016/0020-0190(85)90107-3</a>","chicago":"Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions and Solving the Post-Office Problem in the Plane.” <i>Information Processing Letters</i>. Elsevier, 1985. <a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">https://doi.org/10.1016/0020-0190(85)90107-3</a>.","ista":"Edelsbrunner H, Maurer H. 1985. Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. Information Processing Letters. 21(1), 39–47.","mla":"Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions and Solving the Post-Office Problem in the Plane.” <i>Information Processing Letters</i>, vol. 21, no. 1, Elsevier, 1985, pp. 39–47, doi:<a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">10.1016/0020-0190(85)90107-3</a>.","apa":"Edelsbrunner, H., &#38; Maurer, H. (1985). Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(85)90107-3\">https://doi.org/10.1016/0020-0190(85)90107-3</a>"},"date_created":"2018-12-11T12:07:00Z","publist_id":"2009","year":"1985","acknowledgement":"Research reported in this paper was partially supported by the Austrian Fonds zur Förderung tier wissenschaftlichen\r\nForschung. \r\n","quality_controlled":"1","volume":21,"extern":"1","page":"39 - 47","date_published":"1985-07-10T00:00:00Z","publisher":"Elsevier","abstract":[{"text":"This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ℓ in h, determine a point of P that is hit first when h is rotated around ℓ. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.","lang":"eng"}],"publication_status":"published","publication":"Information Processing Letters","language":[{"iso":"eng"}],"intvolume":"        21","scopus_import":"1","title":"Finding extreme-points in 3-dimensions and solving the post-office problem in the plane","article_processing_charge":"No","issue":"1","date_updated":"2022-01-31T12:49:12Z","type":"journal_article","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","day":"10","oa_version":"None","publication_identifier":{"issn":["0020-0190"],"eissn":["1872-6119"]},"month":"07","author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Maurer, Hermann","first_name":"Hermann","last_name":"Maurer"}]},{"extern":"1","page":"74 - 79","quality_controlled":"1","volume":14,"publisher":"Elsevier","status":"public","type":"journal_article","date_published":"1982-04-20T00:00:00Z","day":"20","oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0020-0190"],"eissn":["1872-6119"]},"month":"04","author":[{"last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"full_name":"Maurer, Hermann","first_name":"Hermann","last_name":"Maurer"},{"first_name":"David","full_name":"Kirkpatrick, David","last_name":"Kirkpatrick"}],"publication_status":"published","doi":"10.1016/0020-0190(82)90090-4","publication":"Information Processing Letters","_id":"4130","article_type":"original","language":[{"iso":"eng"}],"intvolume":"        14","publist_id":"1991","citation":{"apa":"Edelsbrunner, H., Maurer, H., &#38; Kirkpatrick, D. (1982). Polygonal intersection searching. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">https://doi.org/10.1016/0020-0190(82)90090-4</a>","short":"H. Edelsbrunner, H. Maurer, D. Kirkpatrick, Information Processing Letters 14 (1982) 74–79.","ama":"Edelsbrunner H, Maurer H, Kirkpatrick D. Polygonal intersection searching. <i>Information Processing Letters</i>. 1982;14(2):74-79. doi:<a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">10.1016/0020-0190(82)90090-4</a>","ieee":"H. Edelsbrunner, H. Maurer, and D. Kirkpatrick, “Polygonal intersection searching,” <i>Information Processing Letters</i>, vol. 14, no. 2. Elsevier, pp. 74–79, 1982.","chicago":"Edelsbrunner, Herbert, Hermann Maurer, and David Kirkpatrick. “Polygonal Intersection Searching.” <i>Information Processing Letters</i>. Elsevier, 1982. <a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">https://doi.org/10.1016/0020-0190(82)90090-4</a>.","mla":"Edelsbrunner, Herbert, et al. “Polygonal Intersection Searching.” <i>Information Processing Letters</i>, vol. 14, no. 2, Elsevier, 1982, pp. 74–79, doi:<a href=\"https://doi.org/10.1016/0020-0190(82)90090-4\">10.1016/0020-0190(82)90090-4</a>.","ista":"Edelsbrunner H, Maurer H, Kirkpatrick D. 1982. Polygonal intersection searching. Information Processing Letters. 14(2), 74–79."},"title":"Polygonal intersection searching","date_created":"2018-12-11T12:07:07Z","date_updated":"2022-01-21T11:11:25Z","year":"1982","issue":"2","article_processing_charge":"No"},{"_id":"4131","article_type":"original","language":[{"iso":"eng"}],"publication":"Information Processing Letters","doi":"10.1016/0020-0190(82)90068-0","year":"1982","article_processing_charge":"No","issue":"3","date_updated":"2022-01-21T12:22:39Z","citation":{"mla":"Edelsbrunner, Herbert, and Mark Overmars. “On the Equivalence of Some Rectangle Problems.” <i>Information Processing Letters</i>, vol. 14, no. 3, Elsevier, 1982, pp. 124–27, doi:<a href=\"https://doi.org/10.1016/0020-0190(82)90068-0\">10.1016/0020-0190(82)90068-0</a>.","chicago":"Edelsbrunner, Herbert, and Mark Overmars. “On the Equivalence of Some Rectangle Problems.” <i>Information Processing Letters</i>. Elsevier, 1982. <a href=\"https://doi.org/10.1016/0020-0190(82)90068-0\">https://doi.org/10.1016/0020-0190(82)90068-0</a>.","ista":"Edelsbrunner H, Overmars M. 1982. On the equivalence of some rectangle problems. Information Processing Letters. 14(3), 124–127.","short":"H. Edelsbrunner, M. Overmars, Information Processing Letters 14 (1982) 124–127.","ama":"Edelsbrunner H, Overmars M. On the equivalence of some rectangle problems. <i>Information Processing Letters</i>. 1982;14(3):124-127. doi:<a href=\"https://doi.org/10.1016/0020-0190(82)90068-0\">10.1016/0020-0190(82)90068-0</a>","ieee":"H. Edelsbrunner and M. Overmars, “On the equivalence of some rectangle problems,” <i>Information Processing Letters</i>, vol. 14, no. 3. Elsevier, pp. 124–127, 1982.","apa":"Edelsbrunner, H., &#38; Overmars, M. (1982). On the equivalence of some rectangle problems. <i>Information Processing Letters</i>. Elsevier. <a href=\"https://doi.org/10.1016/0020-0190(82)90068-0\">https://doi.org/10.1016/0020-0190(82)90068-0</a>"},"date_created":"2018-12-11T12:07:07Z","publist_id":"1992","title":"On the equivalence of some rectangle problems","intvolume":"        14","status":"public","date_published":"1982-05-16T00:00:00Z","type":"journal_article","publisher":"Elsevier","volume":14,"quality_controlled":"1","page":"124 - 127","extern":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"last_name":"Overmars","first_name":"Mark","full_name":"Overmars, Mark"}],"publication_status":"published","month":"05","publication_identifier":{"eissn":["1872-6119"],"unknown":["0020-0190"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"None","day":"16"}]