[{"issue":"1","related_material":{"record":[{"status":"public","id":"11926","relation":"earlier_version"}]},"volume":55,"language":[{"iso":"eng"}],"publication_identifier":{"issn":["0196-6774"]},"publication_status":"published","month":"04","intvolume":" 55","scopus_import":"1","main_file_link":[{"url":"https://doi.org/10.1016/j.jalgor.2004.11.001","open_access":"1"}],"oa_version":"Published Version","abstract":[{"text":"We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of requests accepted by our algorithm is O((log n + log log M)(log n + log M) log n), where M is the number of multicast groups and n is the number of nodes in the graph. We show that this is close to optimum by presenting an\r\nΩ(log n log M) lower bound on this ratio for any randomized online algorithm against an oblivious adversary, when M is much larger than the link capacities. Our lower bound applies even in the restricted case where the link capacities are much larger than bandwidth requested by a single multicast. We also present a simple proof showing that it is impossible to be competitive against an adaptive online adversary.\r\nAs in the previous online routing algorithms, our algorithm uses edge-costs when deciding on which is the best path to use. In contrast to the previous competitive algorithms in the throughput model, our cost is not a direct function of the edge load. The new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups.","lang":"eng"}],"extern":"1","date_updated":"2023-02-21T16:33:22Z","status":"public","article_type":"original","type":"journal_article","_id":"11763","date_published":"2005-04-01T00:00:00Z","doi":"10.1016/j.jalgor.2004.11.001","date_created":"2022-08-08T12:03:00Z","page":"1-20","day":"01","publication":"Journal of Algorithms","year":"2005","quality_controlled":"1","publisher":"Elsevier","oa":1,"title":"An online throughput-competitive algorithm for multicast routing and admission control","author":[{"full_name":"Goel, Ashish","last_name":"Goel","first_name":"Ashish"},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630"},{"first_name":"Serge","full_name":"Plotkin, Serge","last_name":"Plotkin"}],"article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” Journal of Algorithms. Elsevier, 2005. https://doi.org/10.1016/j.jalgor.2004.11.001.","ista":"Goel A, Henzinger MH, Plotkin S. 2005. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 55(1), 1–20.","mla":"Goel, Ashish, et al. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” Journal of Algorithms, vol. 55, no. 1, Elsevier, 2005, pp. 1–20, doi:10.1016/j.jalgor.2004.11.001.","ieee":"A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm for multicast routing and admission control,” Journal of Algorithms, vol. 55, no. 1. Elsevier, pp. 1–20, 2005.","short":"A. Goel, M.H. Henzinger, S. Plotkin, Journal of Algorithms 55 (2005) 1–20.","apa":"Goel, A., Henzinger, M. H., & Plotkin, S. (2005). An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. Elsevier. https://doi.org/10.1016/j.jalgor.2004.11.001","ama":"Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 2005;55(1):1-20. doi:10.1016/j.jalgor.2004.11.001"}},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","citation":{"mla":"Goel, Ashish, et al. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” Journal of Algorithms, vol. 48, no. 2, Elsevier, 2003, pp. 314–32, doi:10.1016/s0196-6774(03)00054-3.","ieee":"A. Goel, M. H. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers in a network and the set scheduling problem,” Journal of Algorithms, vol. 48, no. 2. Elsevier, pp. 314–332, 2003.","short":"A. Goel, M.H. Henzinger, S. Plotkin, E. Tardos, Journal of Algorithms 48 (2003) 314–332.","ama":"Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 2003;48(2):314-332. doi:10.1016/s0196-6774(03)00054-3","apa":"Goel, A., Henzinger, M. H., Plotkin, S., & Tardos, E. (2003). Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. Elsevier. https://doi.org/10.1016/s0196-6774(03)00054-3","chicago":"Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” Journal of Algorithms. Elsevier, 2003. https://doi.org/10.1016/s0196-6774(03)00054-3.","ista":"Goel A, Henzinger MH, Plotkin S, Tardos E. 2003. Scheduling data transfers in a network and the set scheduling problem. Journal of Algorithms. 48(2), 314–332."},"date_updated":"2022-09-12T09:45:06Z","title":"Scheduling data transfers in a network and the set scheduling problem","article_processing_charge":"No","author":[{"full_name":"Goel, Ashish","last_name":"Goel","first_name":"Ashish"},{"last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"},{"full_name":"Plotkin, Serge","last_name":"Plotkin","first_name":"Serge"},{"first_name":"Eva","last_name":"Tardos","full_name":"Tardos, Eva"}],"_id":"11764","status":"public","article_type":"original","type":"journal_article","publication":"Journal of Algorithms","language":[{"iso":"eng"}],"day":"01","publication_status":"published","year":"2003","publication_identifier":{"issn":["0196-6774"]},"date_created":"2022-08-08T12:09:32Z","volume":48,"issue":"2","date_published":"2003-09-01T00:00:00Z","doi":"10.1016/s0196-6774(03)00054-3","page":"314-332","oa_version":"None","abstract":[{"lang":"eng","text":"In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum."}],"intvolume":" 48","month":"09","scopus_import":"1","publisher":"Elsevier","quality_controlled":"1"},{"citation":{"apa":"Henzinger, M. H., Rao, S., & Gabow, H. N. (2000). Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. Elsevier. https://doi.org/10.1006/jagm.1999.1055","ama":"Henzinger MH, Rao S, Gabow HN. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 2000;34(2):222-250. doi:10.1006/jagm.1999.1055","ieee":"M. H. Henzinger, S. Rao, and H. N. Gabow, “Computing vertex connectivity: New bounds from old techniques,” Journal of Algorithms, vol. 34, no. 2. Elsevier, pp. 222–250, 2000.","short":"M.H. Henzinger, S. Rao, H.N. Gabow, Journal of Algorithms 34 (2000) 222–250.","mla":"Henzinger, Monika H., et al. “Computing Vertex Connectivity: New Bounds from Old Techniques.” Journal of Algorithms, vol. 34, no. 2, Elsevier, 2000, pp. 222–50, doi:10.1006/jagm.1999.1055.","ista":"Henzinger MH, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds from old techniques. Journal of Algorithms. 34(2), 222–250.","chicago":"Henzinger, Monika H, Satish Rao, and Harold N. Gabow. “Computing Vertex Connectivity: New Bounds from Old Techniques.” Journal of Algorithms. Elsevier, 2000. https://doi.org/10.1006/jagm.1999.1055."},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Monika H","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","last_name":"Henzinger","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H"},{"last_name":"Rao","full_name":"Rao, Satish","first_name":"Satish"},{"first_name":"Harold N.","full_name":"Gabow, Harold N.","last_name":"Gabow"}],"article_processing_charge":"No","title":"Computing vertex connectivity: New bounds from old techniques","year":"2000","day":"01","publication":"Journal of Algorithms","page":"222-250","doi":"10.1006/jagm.1999.1055","date_published":"2000-02-01T00:00:00Z","date_created":"2022-07-28T08:56:10Z","quality_controlled":"1","publisher":"Elsevier","date_updated":"2022-09-12T09:06:48Z","extern":"1","_id":"11683","type":"journal_article","article_type":"original","status":"public","keyword":["Computational Theory and Mathematics","Computational Mathematics","Control and Optimization"],"publication_identifier":{"issn":["0196-6774"]},"publication_status":"published","language":[{"iso":"eng"}],"volume":34,"issue":"2","abstract":[{"lang":"eng","text":"The vertex connectivity κ of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the vertex connectivity and a corresponding separator. The time for a digraph having n vertices and m edges is O(min{κ3 + n, κn}m); for an undirected graph the term m can be replaced by κn. A randomized algorithm finds κ with error probability 1/2 in time O(nm). If the vertices have nonnegative weights the weighted vertex connectivity is found in time O(κ1nmlog(n2/m)) where κ1 ≤ m/n is the unweighted vertex connectivity or in expected time O(nmlog(n2/m)) with error probability 1/2. The main algorithm combines two previous vertex connectivity algorithms and a generalization of the preflow-push algorithm of Hao and Orlin (1994, J. Algorithms17, 424–446) that computes edge connectivity."}],"oa_version":"None","scopus_import":"1","month":"02","intvolume":" 34"},{"type":"conference","conference":{"name":"STOC: Symposium on Theory of Computing","start_date":"1999-05-01","location":" Atlanta, GA, United States","end_date":"1999-05-04"},"status":"public","keyword":["Scheduling","Flow time"],"_id":"11691","author":[{"first_name":"Ashish","full_name":"Goel, Ashish","last_name":"Goel"},{"id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H","orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger"},{"first_name":"Serge","full_name":"Plotkin, Serge","last_name":"Plotkin"},{"last_name":"Tardos","full_name":"Tardos, Eva","first_name":"Eva"}],"article_processing_charge":"No","title":"Scheduling data transfers in a network and the set scheduling problem","citation":{"ama":"Goel A, Henzinger MH, Plotkin S, Tardos E. Scheduling data transfers in a network and the set scheduling problem. In: Proceedings of the 31st Annual ACM Symposium on Theory of Computing. Association for Computing Machinery; 1999:189-197. doi:10.1145/301250.301300","apa":"Goel, A., Henzinger, M. H., Plotkin, S., & Tardos, E. (1999). Scheduling data transfers in a network and the set scheduling problem. In Proceedings of the 31st annual ACM symposium on Theory of computing (pp. 189–197). Atlanta, GA, United States: Association for Computing Machinery. https://doi.org/10.1145/301250.301300","ieee":"A. Goel, M. H. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers in a network and the set scheduling problem,” in Proceedings of the 31st annual ACM symposium on Theory of computing, Atlanta, GA, United States, 1999, pp. 189–197.","short":"A. Goel, M.H. Henzinger, S. Plotkin, E. Tardos, in:, Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 1999, pp. 189–197.","mla":"Goel, Ashish, et al. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” Proceedings of the 31st Annual ACM Symposium on Theory of Computing, Association for Computing Machinery, 1999, pp. 189–97, doi:10.1145/301250.301300.","ista":"Goel A, Henzinger MH, Plotkin S, Tardos E. 1999. Scheduling data transfers in a network and the set scheduling problem. Proceedings of the 31st annual ACM symposium on Theory of computing. STOC: Symposium on Theory of Computing, 189–197.","chicago":"Goel, Ashish, Monika H Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling Data Transfers in a Network and the Set Scheduling Problem.” In Proceedings of the 31st Annual ACM Symposium on Theory of Computing, 189–97. Association for Computing Machinery, 1999. https://doi.org/10.1145/301250.301300."},"date_updated":"2023-02-09T11:47:09Z","extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Association for Computing Machinery","scopus_import":"1","quality_controlled":"1","month":"05","abstract":[{"text":"In this paper we consider the online ftp problem. The goal is to service a sequence of file transfer requests given bandwidth constraints of the underlying communication network. The main result of the paper is a technique that leads to algorithms that optimize several natural metrics, such as max-stretch, total flow time, max flow time, and total completion time. In particular, we show how to achieve optimum total flow time and optimum max-stretch if we increase the capacity of the underlying network by a logarithmic factor. We show that the resource augmentation is necessary by proving polynomial lower bounds on the max-stretch and total flow time for the case where online and offline algorithms are using same-capacity edges. Moreover, we also give polylogarithmic lower bounds on the resource augmentation factor necessary in order to keep the total flow time and max-stretch within a constant factor of optimum.","lang":"eng"}],"oa_version":"None","page":"189-197","doi":"10.1145/301250.301300","date_published":"1999-05-01T00:00:00Z","date_created":"2022-07-29T07:43:00Z","publication_identifier":{"issn":["0196-6774"]},"publication_status":"published","year":"1999","day":"01","publication":"Proceedings of the 31st annual ACM symposium on Theory of computing","language":[{"iso":"eng"}]},{"abstract":[{"text":"This paper presents insertions-only algorithms for maintaining the exact and/or approximate size of the minimum edge cut and the minimum vertex cut of a graph. The algorithms output the approximate or exact sizekin timeO(1) and a cut of sizekin time linear in its size. For the minimum edge cut problem and for any 0 < ε ≤ 1, the amortized time per insertion isO(1/ε2) for a (2 + ε)-approximation,O((log λ)((log n)/ε)2) for a (1 + ε)-approximation, andO(λ log n) for the exact size, wherenis the number of nodes in the graph and λ is the size of the minimum cut. The (2 + ε)-approximation algorithm and the exact algorithm are deterministic; the (1 + ε)-approximation algorithm is randomized. We also present a static 2-approximation algorithm for the size κ of the minimum vertex cut in a graph, which takes time. This is a factor of κ faster than the best algorithm for computing the exact size, which takes time. We give an insertions-only algorithm for maintaining a (2 + ε)-approximation of the minimum vertex cut with amortized insertion timeO(n/ε).","lang":"eng"}],"oa_version":"None","quality_controlled":"1","scopus_import":"1","publisher":"Elsevier","month":"07","intvolume":" 24","publication_identifier":{"issn":["0196-6774"]},"publication_status":"published","year":"1997","day":"01","publication":"Journal of Algorithms","language":[{"iso":"eng"}],"page":"194-220","date_published":"1997-07-01T00:00:00Z","issue":"1","doi":"10.1006/jagm.1997.0855","volume":24,"date_created":"2022-08-08T12:18:38Z","_id":"11765","article_type":"original","type":"journal_article","status":"public","date_updated":"2022-09-12T09:15:38Z","citation":{"chicago":"Henzinger, Monika H. “A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” Journal of Algorithms. Elsevier, 1997. https://doi.org/10.1006/jagm.1997.0855.","ista":"Henzinger MH. 1997. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 24(1), 194–220.","mla":"Henzinger, Monika H. “A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” Journal of Algorithms, vol. 24, no. 1, Elsevier, 1997, pp. 194–220, doi:10.1006/jagm.1997.0855.","apa":"Henzinger, M. H. (1997). A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. Elsevier. https://doi.org/10.1006/jagm.1997.0855","ama":"Henzinger MH. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms. 1997;24(1):194-220. doi:10.1006/jagm.1997.0855","short":"M.H. Henzinger, Journal of Algorithms 24 (1997) 194–220.","ieee":"M. H. Henzinger, “A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity,” Journal of Algorithms, vol. 24, no. 1. Elsevier, pp. 194–220, 1997."},"extern":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"orcid":"0000-0002-5008-6530","full_name":"Henzinger, Monika H","last_name":"Henzinger","id":"540c9bbd-f2de-11ec-812d-d04a5be85630","first_name":"Monika H"}],"article_processing_charge":"No","title":"A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity"},{"issue":"3","volume":8,"publication_status":"published","publication_identifier":{"issn":["0196-6774"],"eissn":["1090-2678"]},"language":[{"iso":"eng"}],"main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0196677487900150?via%3Dihub"}],"scopus_import":"1","intvolume":" 8","month":"09","abstract":[{"lang":"eng","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."}],"oa_version":"None","date_updated":"2022-02-03T13:47:53Z","extern":"1","article_type":"original","type":"journal_article","status":"public","_id":"4102","page":"348 - 361","date_created":"2018-12-11T12:06:57Z","doi":"10.1016/0196-6774(87)90015-0","date_published":"1987-09-01T00:00:00Z","year":"1987","publication":"Journal of Algorithms","day":"01","quality_controlled":"1","publisher":"Academic Press","article_processing_charge":"No","author":[{"last_name":"Dobkin","full_name":"Dobkin, David","first_name":"David"},{"first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner"}],"publist_id":"2024","title":"Space searching for intersecting objects","citation":{"chicago":"Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting Objects.” Journal of Algorithms. Academic Press, 1987. https://doi.org/10.1016/0196-6774(87)90015-0.","ista":"Dobkin D, Edelsbrunner H. 1987. Space searching for intersecting objects. Journal of Algorithms. 8(3), 348–361.","mla":"Dobkin, David, and Herbert Edelsbrunner. “Space Searching for Intersecting Objects.” Journal of Algorithms, vol. 8, no. 3, Academic Press, 1987, pp. 348–61, doi:10.1016/0196-6774(87)90015-0.","ama":"Dobkin D, Edelsbrunner H. Space searching for intersecting objects. Journal of Algorithms. 1987;8(3):348-361. doi:10.1016/0196-6774(87)90015-0","apa":"Dobkin, D., & Edelsbrunner, H. (1987). Space searching for intersecting objects. Journal of Algorithms. Academic Press. https://doi.org/10.1016/0196-6774(87)90015-0","short":"D. Dobkin, H. Edelsbrunner, Journal of Algorithms 8 (1987) 348–361.","ieee":"D. Dobkin and H. Edelsbrunner, “Space searching for intersecting objects,” Journal of Algorithms, vol. 8, no. 3. Academic Press, pp. 348–361, 1987."},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"},{"publist_id":"2010","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"first_name":"Mark","last_name":"Overmars","full_name":"Overmars, Mark"}],"article_processing_charge":"No","title":"Batched dynamic solutions to decomposable searching problems","citation":{"apa":"Edelsbrunner, H., & Overmars, M. (1985). Batched dynamic solutions to decomposable searching problems. Journal of Algorithms. Elsevier. https://doi.org/10.1016/0196-6774(85)90030-6","ama":"Edelsbrunner H, Overmars M. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms. 1985;6(4):515-542. doi:10.1016/0196-6774(85)90030-6","short":"H. Edelsbrunner, M. Overmars, Journal of Algorithms 6 (1985) 515–542.","ieee":"H. Edelsbrunner and M. Overmars, “Batched dynamic solutions to decomposable searching problems,” Journal of Algorithms, vol. 6, no. 4. Elsevier, pp. 515–542, 1985.","mla":"Edelsbrunner, Herbert, and Mark Overmars. “Batched Dynamic Solutions to Decomposable Searching Problems.” Journal of Algorithms, vol. 6, no. 4, Elsevier, 1985, pp. 515–42, doi:10.1016/0196-6774(85)90030-6.","ista":"Edelsbrunner H, Overmars M. 1985. Batched dynamic solutions to decomposable searching problems. Journal of Algorithms. 6(4), 515–542.","chicago":"Edelsbrunner, Herbert, and Mark Overmars. “Batched Dynamic Solutions to Decomposable Searching Problems.” Journal of Algorithms. Elsevier, 1985. https://doi.org/10.1016/0196-6774(85)90030-6."},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"515 - 542","date_published":"1985-12-01T00:00:00Z","doi":"10.1016/0196-6774(85)90030-6","date_created":"2018-12-11T12:07:00Z","year":"1985","day":"01","publication":"Journal of Algorithms","quality_controlled":"1","publisher":"Elsevier","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","date_updated":"2022-01-31T13:36:56Z","extern":"1","type":"journal_article","article_type":"original","status":"public","_id":"4112","volume":6,"issue":"4","publication_identifier":{"eissn":["1090-2678"],"issn":["0196-6774"]},"publication_status":"published","language":[{"iso":"eng"}],"scopus_import":"1","month":"12","intvolume":" 6","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"}],"oa_version":"None"},{"article_processing_charge":"No","author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"publist_id":"2007","title":"Computing the extreme distances between two convex polygons","citation":{"ama":"Edelsbrunner H. Computing the extreme distances between two convex polygons. Journal of Algorithms. 1985;6(2):213-224. doi:10.1016/0196-6774(85)90039-2","apa":"Edelsbrunner, H. (1985). Computing the extreme distances between two convex polygons. Journal of Algorithms. Academic Press. https://doi.org/10.1016/0196-6774(85)90039-2","ieee":"H. Edelsbrunner, “Computing the extreme distances between two convex polygons,” Journal of Algorithms, vol. 6, no. 2. Academic Press, pp. 213–224, 1985.","short":"H. Edelsbrunner, Journal of Algorithms 6 (1985) 213–224.","mla":"Edelsbrunner, Herbert. “Computing the Extreme Distances between Two Convex Polygons.” Journal of Algorithms, vol. 6, no. 2, Academic Press, 1985, pp. 213–24, doi:10.1016/0196-6774(85)90039-2.","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.” Journal of Algorithms. Academic Press, 1985. https://doi.org/10.1016/0196-6774(85)90039-2."},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"213 - 224","date_created":"2018-12-11T12:07:01Z","doi":"10.1016/0196-6774(85)90039-2","date_published":"1985-06-01T00:00:00Z","year":"1985","publication":"Journal of Algorithms","day":"01","publisher":"Academic Press","quality_controlled":"1","date_updated":"2022-01-31T10:44:41Z","extern":"1","type":"journal_article","article_type":"original","status":"public","_id":"4115","volume":6,"issue":"2","publication_status":"published","publication_identifier":{"eissn":["1090-2678"],"issn":["0196-6774"]},"language":[{"iso":"eng"}],"scopus_import":"1","intvolume":" 6","month":"06","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)."}],"oa_version":"None"}]