---
_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'
...