Computing the extreme distances between two convex polygons. (English) Zbl 0604.68079

Edelsbrunner, H.

J. Algorithms 6, 213-224 (1985).

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(log m\(+\log n)\) 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 \(\Omega (m+n)\) is proved. This bound is also shown to be best possible by establishing an upper bound of \(O(m+n)\).

MSC:

68R99	Discrete mathematics in relation to computer science
52A10	Convex sets in \(2\) dimensions (including convex curves)
68Q25	Analysis of algorithms and problem complexity

Keywords:

algorithm; minimum distance; maximum distance