Computing the extreme distances between two convex polygons

H. Edelsbrunner, Journal of Algorithms 6 (1985) 213–224.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
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).
Publishing Year
Date Published
1985-06-01
Journal Title
Journal of Algorithms
Volume
6
Issue
2
Page
213 - 224
IST-REx-ID

Cite this

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
Edelsbrunner, H. (1985). Computing the extreme distances between two convex polygons. Journal of Algorithms, 6(2), 213–224. https://doi.org/10.1016/0196-6774(85)90039-2
Edelsbrunner, Herbert. “Computing the Extreme Distances between Two Convex Polygons.” Journal of Algorithms 6, no. 2 (1985): 213–24. https://doi.org/10.1016/0196-6774(85)90039-2.
H. Edelsbrunner, “Computing the extreme distances between two convex polygons,” Journal of Algorithms, vol. 6, no. 2, pp. 213–224, 1985.
Edelsbrunner H. 1985. Computing the extreme distances between two convex polygons. Journal of Algorithms. 6(2), 213–224.
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.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar