TY - JOUR
T1 - Finding the minimum vertex distance between two disjoint convex polygons in linear time
AU - McKenna, Michael
AU - Toussaint, Godfried T.
N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.
PY - 1985/12
Y1 - 1985/12
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=0022188797&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0022188797&partnerID=8YFLogxK
U2 - 10.1016/0898-1221(85)90109-9
DO - 10.1016/0898-1221(85)90109-9
M3 - Article
AN - SCOPUS:0022188797
VL - 11
SP - 1227
EP - 1242
JO - Computers and Mathematics with Applications
JF - Computers and Mathematics with Applications
SN - 0898-1221
IS - 12
ER -