Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace

Mikkel Abrahamsen; Bartosz Walczak

doi:10.1145/3284355

Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace

1 Citation (Scopus)

Abstract

We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons-whether they are nested, overlapping, or disjoint-and our algorithm thus also decides this relationship.

Original language	English
Article number	12
Journal	ACM Transactions on Algorithms
Volume	15
Issue number	1
Pages (from-to)	1-21
ISSN	1549-6325
DOIs	https://doi.org/10.1145/3284355
Publication status	Published - Dec 2018

Access to Document

10.1145/3284355

Cite this

@article{75732c1560724c35a1b5fc67a3d4aa4d,

title = "Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace",

abstract = "We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons-whether they are nested, overlapping, or disjoint-and our algorithm thus also decides this relationship.",

author = "Mikkel Abrahamsen and Bartosz Walczak",

year = "2018",

month = dec,

doi = "10.1145/3284355",

language = "English",

volume = "15",

pages = "1--21",

journal = "ACM Transactions on Algorithms",

issn = "1549-6325",

publisher = "Association for Computing Machinery, Inc.",

number = "1",

}

TY - JOUR

T1 - Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace

AU - Abrahamsen, Mikkel

AU - Walczak, Bartosz

PY - 2018/12

Y1 - 2018/12

N2 - We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons-whether they are nested, overlapping, or disjoint-and our algorithm thus also decides this relationship.

AB - We provide a remarkably simple algorithm to compute all (at most four) common tangents of two disjoint simple polygons. Given each polygon as a read-only array of its corners in cyclic order, the algorithm runs in linear time and constant workspace and is the first to achieve the two complexity bounds simultaneously. The set of common tangents provides basic information about the convex hulls of the polygons-whether they are nested, overlapping, or disjoint-and our algorithm thus also decides this relationship.

U2 - 10.1145/3284355

DO - 10.1145/3284355

M3 - Journal article

SN - 1549-6325

VL - 15

SP - 1

EP - 21

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

IS - 1

M1 - 12

ER -

Common Tangents of Two Disjoint Polygons in Linear Time and Constant Workspace

Abstract

Access to Document

Fingerprint

Cite this