License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.198
URN: urn:nbn:de:0030-drops-51313
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5131/
Go to the corresponding LIPIcs Volume Portal

Abrahamsen, Mikkel

An Optimal Algorithm for the Separating Common Tangents of Two Polygons

pdf-format:
48.pdf (0.4 MB)

Abstract

We describe an algorithm for computing the separating common tangents of two simple polygons using linear time and only constant workspace. A tangent of a polygon is a line touching the polygon such that all of the polygon lies to the same side of the line. A separating common tangent of two polygons is a tangent of both polygons where the polygons are lying on different sides of the tangent. Each polygon is given as a read-only array of its corners. If a separating common tangent does not exist, the algorithm reports that. Otherwise, two corners defining a separating common tangent are returned. The algorithm is simple and implies an optimal algorithm for deciding if the convex hulls of two polygons are disjoint or not. This was not known to be possible in linear time and constant workspace prior to this paper.

An outer common tangent is a tangent of both polygons where the polygons are on the same side of the tangent. In the case where the convex hulls of the polygons are disjoint, we give an algorithm for computing the outer common tangents in linear time using constant workspace.

BibTeX - Entry

@InProceedings{abrahamsen:LIPIcs:2015:5131,
  author =	{Mikkel Abrahamsen},
  title =	{{An Optimal Algorithm for the Separating Common Tangents of Two Polygons}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{198--208},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5131},
  URN =		{urn:nbn:de:0030-drops-51313},
  doi =		{10.4230/LIPIcs.SOCG.2015.198},
  annote =	{Keywords: planar computational geometry, simple polygon, common tangent, optimal algorithm, constant workspace}
}

Keywords: planar computational geometry, simple polygon, common tangent, optimal algorithm, constant workspace
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI