---
_id: '11763'
abstract:
- lang: eng
  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."
article_processing_charge: No
article_type: original
author:
- first_name: Ashish
  full_name: Goel, Ashish
  last_name: Goel
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Serge
  full_name: Plotkin, Serge
  last_name: Plotkin
citation:
  ama: Goel A, Henzinger M, Plotkin S. An online throughput-competitive algorithm
    for multicast routing and admission control. <i>Journal of Algorithms</i>. 2005;55(1):1-20.
    doi:<a href="https://doi.org/10.1016/j.jalgor.2004.11.001">10.1016/j.jalgor.2004.11.001</a>
  apa: Goel, A., Henzinger, M., &#38; Plotkin, S. (2005). An online throughput-competitive
    algorithm for multicast routing and admission control. <i>Journal of Algorithms</i>.
    Elsevier. <a href="https://doi.org/10.1016/j.jalgor.2004.11.001">https://doi.org/10.1016/j.jalgor.2004.11.001</a>
  chicago: Goel, Ashish, Monika Henzinger, and Serge Plotkin. “An Online Throughput-Competitive
    Algorithm for Multicast Routing and Admission Control.” <i>Journal of Algorithms</i>.
    Elsevier, 2005. <a href="https://doi.org/10.1016/j.jalgor.2004.11.001">https://doi.org/10.1016/j.jalgor.2004.11.001</a>.
  ieee: A. Goel, M. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm
    for multicast routing and admission control,” <i>Journal of Algorithms</i>, vol.
    55, no. 1. Elsevier, pp. 1–20, 2005.
  ista: Goel A, Henzinger M, 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.” <i>Journal of Algorithms</i>, vol. 55, no. 1,
    Elsevier, 2005, pp. 1–20, doi:<a href="https://doi.org/10.1016/j.jalgor.2004.11.001">10.1016/j.jalgor.2004.11.001</a>.
  short: A. Goel, M. Henzinger, S. Plotkin, Journal of Algorithms 55 (2005) 1–20.
date_created: 2022-08-08T12:03:00Z
date_published: 2005-04-01T00:00:00Z
date_updated: 2024-11-06T08:12:50Z
day: '01'
doi: 10.1016/j.jalgor.2004.11.001
extern: '1'
intvolume: '        55'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1016/j.jalgor.2004.11.001
month: '04'
oa: 1
oa_version: Published Version
page: 1-20
publication: Journal of Algorithms
publication_identifier:
  issn:
  - 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
related_material:
  record:
  - id: '11926'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: An online throughput-competitive algorithm for multicast routing and admission
  control
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 55
year: '2005'
...
---
_id: '11764'
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.
article_processing_charge: No
article_type: original
author:
- first_name: Ashish
  full_name: Goel, Ashish
  last_name: Goel
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Serge
  full_name: Plotkin, Serge
  last_name: Plotkin
- first_name: Eva
  full_name: Tardos, Eva
  last_name: Tardos
citation:
  ama: Goel A, Henzinger M, Plotkin S, Tardos E. Scheduling data transfers in a network
    and the set scheduling problem. <i>Journal of Algorithms</i>. 2003;48(2):314-332.
    doi:<a href="https://doi.org/10.1016/s0196-6774(03)00054-3">10.1016/s0196-6774(03)00054-3</a>
  apa: Goel, A., Henzinger, M., Plotkin, S., &#38; Tardos, E. (2003). Scheduling data
    transfers in a network and the set scheduling problem. <i>Journal of Algorithms</i>.
    Elsevier. <a href="https://doi.org/10.1016/s0196-6774(03)00054-3">https://doi.org/10.1016/s0196-6774(03)00054-3</a>
  chicago: Goel, Ashish, Monika Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling
    Data Transfers in a Network and the Set Scheduling Problem.” <i>Journal of Algorithms</i>.
    Elsevier, 2003. <a href="https://doi.org/10.1016/s0196-6774(03)00054-3">https://doi.org/10.1016/s0196-6774(03)00054-3</a>.
  ieee: A. Goel, M. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers
    in a network and the set scheduling problem,” <i>Journal of Algorithms</i>, vol.
    48, no. 2. Elsevier, pp. 314–332, 2003.
  ista: Goel A, Henzinger M, Plotkin S, Tardos E. 2003. Scheduling data transfers
    in a network and the set scheduling problem. Journal of Algorithms. 48(2), 314–332.
  mla: Goel, Ashish, et al. “Scheduling Data Transfers in a Network and the Set Scheduling
    Problem.” <i>Journal of Algorithms</i>, vol. 48, no. 2, Elsevier, 2003, pp. 314–32,
    doi:<a href="https://doi.org/10.1016/s0196-6774(03)00054-3">10.1016/s0196-6774(03)00054-3</a>.
  short: A. Goel, M. Henzinger, S. Plotkin, E. Tardos, Journal of Algorithms 48 (2003)
    314–332.
date_created: 2022-08-08T12:09:32Z
date_published: 2003-09-01T00:00:00Z
date_updated: 2024-11-06T08:21:48Z
day: '01'
doi: 10.1016/s0196-6774(03)00054-3
extern: '1'
intvolume: '        48'
issue: '2'
language:
- iso: eng
month: '09'
oa_version: None
page: 314-332
publication: Journal of Algorithms
publication_identifier:
  issn:
  - 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Scheduling data transfers in a network and the set scheduling problem
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 48
year: '2003'
...
---
_id: '11683'
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.
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Satish
  full_name: Rao, Satish
  last_name: Rao
- first_name: Harold N.
  full_name: Gabow, Harold N.
  last_name: Gabow
citation:
  ama: 'Henzinger M, Rao S, Gabow HN. Computing vertex connectivity: New bounds from
    old techniques. <i>Journal of Algorithms</i>. 2000;34(2):222-250. doi:<a href="https://doi.org/10.1006/jagm.1999.1055">10.1006/jagm.1999.1055</a>'
  apa: 'Henzinger, M., Rao, S., &#38; Gabow, H. N. (2000). Computing vertex connectivity:
    New bounds from old techniques. <i>Journal of Algorithms</i>. Elsevier. <a href="https://doi.org/10.1006/jagm.1999.1055">https://doi.org/10.1006/jagm.1999.1055</a>'
  chicago: 'Henzinger, Monika, Satish Rao, and Harold N. Gabow. “Computing Vertex
    Connectivity: New Bounds from Old Techniques.” <i>Journal of Algorithms</i>. Elsevier,
    2000. <a href="https://doi.org/10.1006/jagm.1999.1055">https://doi.org/10.1006/jagm.1999.1055</a>.'
  ieee: 'M. Henzinger, S. Rao, and H. N. Gabow, “Computing vertex connectivity: New
    bounds from old techniques,” <i>Journal of Algorithms</i>, vol. 34, no. 2. Elsevier,
    pp. 222–250, 2000.'
  ista: 'Henzinger M, Rao S, Gabow HN. 2000. Computing vertex connectivity: New bounds
    from old techniques. Journal of Algorithms. 34(2), 222–250.'
  mla: 'Henzinger, Monika, et al. “Computing Vertex Connectivity: New Bounds from
    Old Techniques.” <i>Journal of Algorithms</i>, vol. 34, no. 2, Elsevier, 2000,
    pp. 222–50, doi:<a href="https://doi.org/10.1006/jagm.1999.1055">10.1006/jagm.1999.1055</a>.'
  short: M. Henzinger, S. Rao, H.N. Gabow, Journal of Algorithms 34 (2000) 222–250.
date_created: 2022-07-28T08:56:10Z
date_published: 2000-02-01T00:00:00Z
date_updated: 2024-11-04T11:42:08Z
day: '01'
doi: 10.1006/jagm.1999.1055
extern: '1'
intvolume: '        34'
issue: '2'
keyword:
- Computational Theory and Mathematics
- Computational Mathematics
- Control and Optimization
language:
- iso: eng
month: '02'
oa_version: None
page: 222-250
publication: Journal of Algorithms
publication_identifier:
  issn:
  - 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Computing vertex connectivity: New bounds from old techniques'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 34
year: '2000'
...
---
_id: '11691'
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.
article_processing_charge: No
author:
- first_name: Ashish
  full_name: Goel, Ashish
  last_name: Goel
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Serge
  full_name: Plotkin, Serge
  last_name: Plotkin
- first_name: Eva
  full_name: Tardos, Eva
  last_name: Tardos
citation:
  ama: 'Goel A, Henzinger M, Plotkin S, Tardos E. Scheduling data transfers in a network
    and the set scheduling problem. In: <i>Proceedings of the 31st Annual ACM Symposium
    on Theory of Computing</i>. Association for Computing Machinery; 1999:189-197.
    doi:<a href="https://doi.org/10.1145/301250.301300">10.1145/301250.301300</a>'
  apa: 'Goel, A., Henzinger, M., Plotkin, S., &#38; Tardos, E. (1999). Scheduling
    data transfers in a network and the set scheduling problem. In <i>Proceedings
    of the 31st annual ACM symposium on Theory of computing</i> (pp. 189–197).  Atlanta,
    GA, United States: Association for Computing Machinery. <a href="https://doi.org/10.1145/301250.301300">https://doi.org/10.1145/301250.301300</a>'
  chicago: Goel, Ashish, Monika Henzinger, Serge Plotkin, and Eva Tardos. “Scheduling
    Data Transfers in a Network and the Set Scheduling Problem.” In <i>Proceedings
    of the 31st Annual ACM Symposium on Theory of Computing</i>, 189–97. Association
    for Computing Machinery, 1999. <a href="https://doi.org/10.1145/301250.301300">https://doi.org/10.1145/301250.301300</a>.
  ieee: A. Goel, M. Henzinger, S. Plotkin, and E. Tardos, “Scheduling data transfers
    in a network and the set scheduling problem,” in <i>Proceedings of the 31st annual
    ACM symposium on Theory of computing</i>,  Atlanta, GA, United States, 1999, pp.
    189–197.
  ista: 'Goel A, Henzinger M, 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.'
  mla: Goel, Ashish, et al. “Scheduling Data Transfers in a Network and the Set Scheduling
    Problem.” <i>Proceedings of the 31st Annual ACM Symposium on Theory of Computing</i>,
    Association for Computing Machinery, 1999, pp. 189–97, doi:<a href="https://doi.org/10.1145/301250.301300">10.1145/301250.301300</a>.
  short: A. Goel, M. 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.
conference:
  end_date: 1999-05-04
  location: ' Atlanta, GA, United States'
  name: 'STOC: Symposium on Theory of Computing'
  start_date: 1999-05-01
date_created: 2022-07-29T07:43:00Z
date_published: 1999-05-01T00:00:00Z
date_updated: 2024-11-06T12:08:56Z
day: '01'
doi: 10.1145/301250.301300
extern: '1'
keyword:
- Scheduling
- Flow time
language:
- iso: eng
month: '05'
oa_version: None
page: 189-197
publication: Proceedings of the 31st annual ACM symposium on Theory of computing
publication_identifier:
  issn:
  - 0196-6774
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Scheduling data transfers in a network and the set scheduling problem
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '1999'
...
---
_id: '11765'
abstract:
- lang: eng
  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/ε).
article_processing_charge: No
article_type: original
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: Henzinger M. A static 2-approximation algorithm for vertex connectivity and
    incremental approximation algorithms for edge and vertex connectivity. <i>Journal
    of Algorithms</i>. 1997;24(1):194-220. doi:<a href="https://doi.org/10.1006/jagm.1997.0855">10.1006/jagm.1997.0855</a>
  apa: Henzinger, M. (1997). A static 2-approximation algorithm for vertex connectivity
    and incremental approximation algorithms for edge and vertex connectivity. <i>Journal
    of Algorithms</i>. Elsevier. <a href="https://doi.org/10.1006/jagm.1997.0855">https://doi.org/10.1006/jagm.1997.0855</a>
  chicago: Henzinger, Monika. “A Static 2-Approximation Algorithm for Vertex Connectivity
    and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” <i>Journal
    of Algorithms</i>. Elsevier, 1997. <a href="https://doi.org/10.1006/jagm.1997.0855">https://doi.org/10.1006/jagm.1997.0855</a>.
  ieee: M. Henzinger, “A static 2-approximation algorithm for vertex connectivity
    and incremental approximation algorithms for edge and vertex connectivity,” <i>Journal
    of Algorithms</i>, vol. 24, no. 1. Elsevier, pp. 194–220, 1997.
  ista: Henzinger M. 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. “A Static 2-Approximation Algorithm for Vertex Connectivity
    and Incremental Approximation Algorithms for Edge and Vertex Connectivity.” <i>Journal
    of Algorithms</i>, vol. 24, no. 1, Elsevier, 1997, pp. 194–220, doi:<a href="https://doi.org/10.1006/jagm.1997.0855">10.1006/jagm.1997.0855</a>.
  short: M. Henzinger, Journal of Algorithms 24 (1997) 194–220.
date_created: 2022-08-08T12:18:38Z
date_published: 1997-07-01T00:00:00Z
date_updated: 2024-11-06T08:22:00Z
day: '01'
doi: 10.1006/jagm.1997.0855
extern: '1'
intvolume: '        24'
issue: '1'
language:
- iso: eng
month: '07'
oa_version: None
page: 194-220
publication: Journal of Algorithms
publication_identifier:
  issn:
  - 0196-6774
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: A static 2-approximation algorithm for vertex connectivity and incremental
  approximation algorithms for edge and vertex connectivity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 24
year: '1997'
...
---
_id: '4102'
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.
article_processing_charge: No
article_type: original
author:
- first_name: David
  full_name: Dobkin, David
  last_name: Dobkin
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  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>
  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>
  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>.
  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.
  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.” <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>.
  short: D. Dobkin, H. Edelsbrunner, Journal of Algorithms 8 (1987) 348–361.
date_created: 2018-12-11T12:06:57Z
date_published: 1987-09-01T00:00:00Z
date_updated: 2022-02-03T13:47:53Z
day: '01'
doi: 10.1016/0196-6774(87)90015-0
extern: '1'
intvolume: '         8'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0196677487900150?via%3Dihub
month: '09'
oa_version: None
page: 348 - 361
publication: Journal of Algorithms
publication_identifier:
  eissn:
  - 1090-2678
  issn:
  - 0196-6774
publication_status: published
publisher: Academic Press
publist_id: '2024'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space searching for intersecting objects
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 8
year: '1987'
...
---
_id: '4112'
abstract:
- lang: eng
  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.'
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"
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Mark
  full_name: Overmars, Mark
  last_name: Overmars
citation:
  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>
  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>
  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>.
  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.
  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>.
  short: H. Edelsbrunner, M. Overmars, Journal of Algorithms 6 (1985) 515–542.
date_created: 2018-12-11T12:07:00Z
date_published: 1985-12-01T00:00:00Z
date_updated: 2022-01-31T13:36:56Z
day: '01'
doi: 10.1016/0196-6774(85)90030-6
extern: '1'
intvolume: '         6'
issue: '4'
language:
- iso: eng
month: '12'
oa_version: None
page: 515 - 542
publication: Journal of Algorithms
publication_identifier:
  eissn:
  - 1090-2678
  issn:
  - 0196-6774
publication_status: published
publisher: Elsevier
publist_id: '2010'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Batched dynamic solutions to decomposable searching problems
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 6
year: '1985'
...
---
_id: '4115'
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).
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
citation:
  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>
  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>
  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>.
  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.
  ista: Edelsbrunner H. 1985. Computing the extreme distances between two convex polygons.
    Journal of Algorithms. 6(2), 213–224.
  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>.
  short: H. Edelsbrunner, Journal of Algorithms 6 (1985) 213–224.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-06-01T00:00:00Z
date_updated: 2022-01-31T10:44:41Z
day: '01'
doi: 10.1016/0196-6774(85)90039-2
extern: '1'
intvolume: '         6'
issue: '2'
language:
- iso: eng
month: '06'
oa_version: None
page: 213 - 224
publication: Journal of Algorithms
publication_identifier:
  eissn:
  - 1090-2678
  issn:
  - 0196-6774
publication_status: published
publisher: Academic Press
publist_id: '2007'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing the extreme distances between two convex polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 6
year: '1985'
...