Let V = v1, v2, ..., vm and W = w1, w2, ..., wn be two linearly separable convex polygons whose vertices are specified by their cartesian coordinates in order. An algorithm with O(m + n) worst-case time complexity is described for finding the minimum euclidean distance between a vertex v1 in V and a vertex wj in W. It is also shown that the algorithm is optimal.
ASJC Scopus subject areas
- Modeling and Simulation
- Computational Theory and Mathematics
- Computational Mathematics