Finding the minimum vertex distance between two disjoint convex polygons in linear time

Michael McKenna; Godfried T. Toussaint

doi:10.1016/0898-1221(85)90109-9

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Michael McKenna, Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Let V = v₁, v₂, ..., v_m and W = w₁, w₂, ..., w_n 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 v₁ in V and a vertex w_j in W. It is also shown that the algorithm is optimal.

Original language	English (US)
Pages (from-to)	1227-1242
Number of pages	16
Journal	Computers and Mathematics with Applications
Volume	11
Issue number	12
DOIs	https://doi.org/10.1016/0898-1221(85)90109-9
State	Published - Dec 1985

ASJC Scopus subject areas

Modeling and Simulation
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1016/0898-1221(85)90109-9

Cite this

@article{cbef34598b46487bb6cb2266da8f96ae,

title = "Finding the minimum vertex distance between two disjoint convex polygons in linear time",

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.",

author = "Michael McKenna and Toussaint, {Godfried T.}",

year = "1985",

month = dec,

doi = "10.1016/0898-1221(85)90109-9",

language = "English (US)",

volume = "11",

pages = "1227--1242",

journal = "Computers and Mathematics with Applications",

issn = "0898-1221",

publisher = "Elsevier Limited",

number = "12",

}

TY - JOUR

T1 - Finding the minimum vertex distance between two disjoint convex polygons in linear time

AU - McKenna, Michael

AU - Toussaint, Godfried T.

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 -

Finding the minimum vertex distance between two disjoint convex polygons in linear time

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this