[{"_id":"4102","article_type":"original","doi":"10.1016/0196-6774(87)90015-0","year":"1987","publist_id":"2024","citation":{"short":"D. Dobkin, H. Edelsbrunner, Journal of Algorithms 8 (1987) 348–361.","ieee":"D. Dobkin and H. Edelsbrunner, “Space searching for intersecting objects,” <i>Journal of Algorithms</i>, vol. 8, no. 3. Academic Press, pp. 348–361, 1987.","ama":"Dobkin D, Edelsbrunner H. Space searching for intersecting objects. <i>Journal of Algorithms</i>. 1987;8(3):348-361. doi:<a href=\"https://doi.org/10.1016/0196-6774(87)90015-0\">10.1016/0196-6774(87)90015-0</a>","chicago":"Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting Objects.” <i>Journal of Algorithms</i>. Academic Press, 1987. <a href=\"https://doi.org/10.1016/0196-6774(87)90015-0\">https://doi.org/10.1016/0196-6774(87)90015-0</a>.","mla":"Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting Objects.” <i>Journal of Algorithms</i>, vol. 8, no. 3, Academic Press, 1987, pp. 348–61, doi:<a href=\"https://doi.org/10.1016/0196-6774(87)90015-0\">10.1016/0196-6774(87)90015-0</a>.","ista":"Dobkin D, Edelsbrunner H. 1987. Space searching for intersecting objects. Journal of Algorithms. 8(3), 348–361.","apa":"Dobkin, D., &#38; Edelsbrunner, H. (1987). Space searching for intersecting objects. <i>Journal of Algorithms</i>. Academic Press. <a href=\"https://doi.org/10.1016/0196-6774(87)90015-0\">https://doi.org/10.1016/0196-6774(87)90015-0</a>"},"date_created":"2018-12-11T12:06:57Z","publisher":"Academic Press","date_published":"1987-09-01T00:00:00Z","extern":"1","page":"348 - 361","volume":8,"quality_controlled":"1","publication_status":"published","abstract":[{"text":"Determining or counting geometric objects that intersect another geometric query object is at the core of algorithmic problems in a number of applied areas of computer science. This article presents a family of space-efficient data structures that realize sublinear query time for points, line segments, lines and polygons in the plane, and points, line segments, planes, and polyhedra in three dimensions.","lang":"eng"}],"language":[{"iso":"eng"}],"publication":"Journal of Algorithms","date_updated":"2022-02-03T13:47:53Z","article_processing_charge":"No","issue":"3","title":"Space searching for intersecting objects","intvolume":"         8","scopus_import":"1","type":"journal_article","status":"public","author":[{"first_name":"David","full_name":"Dobkin, David","last_name":"Dobkin"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"}],"month":"09","publication_identifier":{"eissn":["1090-2678"],"issn":["0196-6774"]},"day":"01","oa_version":"None","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0196677487900150?via%3Dihub"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},{"publication_status":"published","abstract":[{"text":"The batched static version of a searching problem asks for performing a given set of queries on a given set of objects. All queries are known in advance. The batched dynamic version of a searching problem is the following: given a sequence of insertions, deletions, and queries, perform them on an initially empty set. We will develop methods for solving batched static and batched dynamic versions of searching problems which are in particular applicable to decomposable searching problems. The techniques show that batched static (dynamic) versions of searching problems can often be solved more efficiently than by using known static (dynamic) data structures. In particular, a technique called “streaming” is described that reduces the space requirements considerably. The methods have also a number of applications on set problems. E.g., the k intersecting pairs in a set of n axis-parallel hyper-rectangles in d dimensions can be reported in O (nlogd−1n + k) time using only O(n) space.","lang":"eng"}],"publisher":"Elsevier","date_published":"1985-12-01T00:00:00Z","page":"515 - 542","extern":"1","quality_controlled":"1","volume":6,"acknowledgement":"Research reported in this paper was done while the second author visited the University of Graz. The first author was supported by the Austrian Fonds zur Förderung der Wissenschaftlichen Forschung. The second author was supported by the Netherlands Organization for the Advancement of Pure Research (ZWO). \r\n","year":"1985","citation":{"ista":"Edelsbrunner H, Overmars M. 1985. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms. 6(4), 515–542.","mla":"Edelsbrunner, Herbert, and Mark Overmars. “Batched Dynamic Solutions to Decomposable Searching Problems.” <i>Journal of Algorithms</i>, vol. 6, no. 4, Elsevier, 1985, pp. 515–42, doi:<a href=\"https://doi.org/10.1016/0196-6774(85)90030-6\">10.1016/0196-6774(85)90030-6</a>.","chicago":"Edelsbrunner, Herbert, and Mark Overmars. “Batched Dynamic Solutions to Decomposable Searching Problems.” <i>Journal of Algorithms</i>. Elsevier, 1985. <a href=\"https://doi.org/10.1016/0196-6774(85)90030-6\">https://doi.org/10.1016/0196-6774(85)90030-6</a>.","short":"H. Edelsbrunner, M. Overmars, Journal of Algorithms 6 (1985) 515–542.","ama":"Edelsbrunner H, Overmars M. Batched dynamic solutions to decomposable searching problems. <i>Journal of Algorithms</i>. 1985;6(4):515-542. doi:<a href=\"https://doi.org/10.1016/0196-6774(85)90030-6\">10.1016/0196-6774(85)90030-6</a>","ieee":"H. Edelsbrunner and M. Overmars, “Batched dynamic solutions to decomposable searching problems,” <i>Journal of Algorithms</i>, vol. 6, no. 4. Elsevier, pp. 515–542, 1985.","apa":"Edelsbrunner, H., &#38; Overmars, M. (1985). Batched dynamic solutions to decomposable searching problems. <i>Journal of Algorithms</i>. Elsevier. <a href=\"https://doi.org/10.1016/0196-6774(85)90030-6\">https://doi.org/10.1016/0196-6774(85)90030-6</a>"},"date_created":"2018-12-11T12:07:00Z","publist_id":"2010","article_type":"original","_id":"4112","doi":"10.1016/0196-6774(85)90030-6","author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"first_name":"Mark","full_name":"Overmars, Mark","last_name":"Overmars"}],"publication_identifier":{"issn":["0196-6774"],"eissn":["1090-2678"]},"month":"12","oa_version":"None","day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","type":"journal_article","status":"public","date_updated":"2022-01-31T13:36:56Z","issue":"4","article_processing_charge":"No","title":"Batched dynamic solutions to decomposable searching problems","intvolume":"         6","scopus_import":"1","language":[{"iso":"eng"}],"publication":"Journal of Algorithms"},{"_id":"4115","article_type":"original","doi":"10.1016/0196-6774(85)90039-2","citation":{"apa":"Edelsbrunner, H. (1985). Computing the extreme distances between two convex polygons. <i>Journal of Algorithms</i>. Academic Press. <a href=\"https://doi.org/10.1016/0196-6774(85)90039-2\">https://doi.org/10.1016/0196-6774(85)90039-2</a>","ista":"Edelsbrunner H. 1985. Computing the extreme distances between two convex polygons. Journal of Algorithms. 6(2), 213–224.","chicago":"Edelsbrunner, Herbert. “Computing the Extreme Distances between Two Convex Polygons.” <i>Journal of Algorithms</i>. Academic Press, 1985. <a href=\"https://doi.org/10.1016/0196-6774(85)90039-2\">https://doi.org/10.1016/0196-6774(85)90039-2</a>.","mla":"Edelsbrunner, Herbert. “Computing the Extreme Distances between Two Convex Polygons.” <i>Journal of Algorithms</i>, vol. 6, no. 2, Academic Press, 1985, pp. 213–24, doi:<a href=\"https://doi.org/10.1016/0196-6774(85)90039-2\">10.1016/0196-6774(85)90039-2</a>.","ama":"Edelsbrunner H. Computing the extreme distances between two convex polygons. <i>Journal of Algorithms</i>. 1985;6(2):213-224. doi:<a href=\"https://doi.org/10.1016/0196-6774(85)90039-2\">10.1016/0196-6774(85)90039-2</a>","ieee":"H. Edelsbrunner, “Computing the extreme distances between two convex polygons,” <i>Journal of Algorithms</i>, vol. 6, no. 2. Academic Press, pp. 213–224, 1985.","short":"H. Edelsbrunner, Journal of Algorithms 6 (1985) 213–224."},"date_created":"2018-12-11T12:07:01Z","publist_id":"2007","year":"1985","extern":"1","page":"213 - 224","quality_controlled":"1","volume":6,"publisher":"Academic Press","date_published":"1985-06-01T00:00:00Z","publication_status":"published","abstract":[{"lang":"eng","text":"A polygon in the plane is convex if it contains all line segments connecting any two of its points. Let P and Q denote two convex polygons. The computational complexity of finding the minimum and maximum distance possible between two points p in P and q in Q is studied. An algorithm is described that determines the minimum distance (together with points p and q that realize it) in O(logm + logn) time, where m and n denote the number of vertices of P and Q, respectively. This is optimal in the worst case. For computing the maximum distance, a lower bound Ω(m + n) is proved. This bound is also shown to be best possible by establishing an upper bound of O(m + n)."}],"language":[{"iso":"eng"}],"publication":"Journal of Algorithms","title":"Computing the extreme distances between two convex polygons","date_updated":"2022-01-31T10:44:41Z","article_processing_charge":"No","issue":"2","scopus_import":"1","intvolume":"         6","type":"journal_article","status":"public","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"}],"oa_version":"None","day":"01","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publication_identifier":{"issn":["0196-6774"],"eissn":["1090-2678"]},"month":"06"}]