An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons

G. T. Toussaint

doi:10.1007/BF02243778

An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons

G. T. Toussaint

Computer Science

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

Abstract

Let P={p₁, p₂, ..., p_m} and Q={q₁, q₂, ..., q_n} be two intersecting convex polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m+n) algorithm is presented for computing the minimum euclidean distance betweena vertex p_i in P and a vertex q_j in Q.

Original language	English (US)
Pages (from-to)	357-364
Number of pages	8
Journal	Computing
Volume	32
Issue number	4
DOIs	https://doi.org/10.1007/BF02243778
State	Published - Dec 1984

Keywords

Algorithms
Voronoi diagrams
complexity
computational geometry
convex polygons
minimum distance

ASJC Scopus subject areas

Software
Theoretical Computer Science
Numerical Analysis
Computer Science Applications
Computational Theory and Mathematics
Computational Mathematics

Access to Document

10.1007/BF02243778

Cite this

@article{0d40a742ae064d5dbbd58e2839b54dc5,

title = "An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons",

abstract = "Let P={p1, p2, ..., pm} and Q={q1, q2, ..., qn} be two intersecting convex polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m+n) algorithm is presented for computing the minimum euclidean distance betweena vertex pi in P and a vertex qj in Q.",

keywords = "Algorithms, Voronoi diagrams, complexity, computational geometry, convex polygons, minimum distance",

author = "Toussaint, {G. T.}",

year = "1984",

month = dec,

doi = "10.1007/BF02243778",

language = "English (US)",

volume = "32",

pages = "357--364",

journal = "Computing",

issn = "0010-485X",

publisher = "Springer Wien",

number = "4",

}

TY - JOUR

T1 - An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons

AU - Toussaint, G. T.

PY - 1984/12

Y1 - 1984/12

N2 - Let P={p1, p2, ..., pm} and Q={q1, q2, ..., qn} be two intersecting convex polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m+n) algorithm is presented for computing the minimum euclidean distance betweena vertex pi in P and a vertex qj in Q.

AB - Let P={p1, p2, ..., pm} and Q={q1, q2, ..., qn} be two intersecting convex polygons whose vertices are specified by their cartesian coordinates in order. An optimal O(m+n) algorithm is presented for computing the minimum euclidean distance betweena vertex pi in P and a vertex qj in Q.

KW - Algorithms

KW - Voronoi diagrams

KW - complexity

KW - computational geometry

KW - convex polygons

KW - minimum distance

UR - http://www.scopus.com/inward/record.url?scp=0021290263&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021290263&partnerID=8YFLogxK

U2 - 10.1007/BF02243778

DO - 10.1007/BF02243778

M3 - Article

AN - SCOPUS:0021290263

SN - 0010-485X

VL - 32

SP - 357

EP - 364

JO - Computing

JF - Computing

IS - 4

ER -

An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this