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