Finding the minimum vertex distance between two disjoint convex polygons in linear time |
| |
Authors: | Michael McKenna Godfried T Toussaint |
| |
Affiliation: | School of Computer Science, McGill University, 805 Sherbrooke Street West, Montreal, Quebec, Canada H3A 2K6 |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|