---
res:
bibo_abstract:
- 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).@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Herbert
foaf_name: Edelsbrunner, Herbert
foaf_surname: Edelsbrunner
foaf_workInfoHomepage: http://www.librecat.org/personId=3FB178DA-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-9823-6833
bibo_doi: 10.1016/0196-6774(85)90039-2
bibo_issue: '2'
bibo_volume: 6
dct_date: 1985^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/0196-6774
- http://id.crossref.org/issn/1090-2678
dct_language: eng
dct_publisher: Academic Press@
dct_title: Computing the extreme distances between two convex polygons@
...