Common tangents of two disjoint polygons in linear time and constant workspace

DOI10.1145/3284355MaRDI QIDQ4629982zbMATH OpenOpenAlexWikidataFDO

Authors Mikkel Abrahamsen, Bartosz Walczak

Publication date 28 March 2019

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.01816

zbMATH Keywords

common tangentconstant workspacesimple polygon

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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.

Recommendations

• An optimal algorithm for the separating common tangents of two polygons
• scientific article; zbMATH DE number 6846375
• Computing common tangents without a separating line
• Parallel algorithms for some functions of two convex polygons
• Three problems about simple polygons

Cited in

(5)

• scientific article; zbMATH DE number 6846375 (Why is no real title available?)
• Computing common tangents without a separating line
• An optimal algorithm for the separating common tangents of two polygons
• The geodesic edge center of a simple polygon
• Polynomial-time algorithms for contiguous art gallery and related problems

This page was built for publication: Common tangents of two disjoint polygons in linear time and constant workspace

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4629982)