On separating two simple polygons by a single translation

Research output: Contribution to journalArticle

Abstract

Let P and Q be two disjoint simple polygons having n sides each. We present an algorithm which determines whether Q can be moved by a single translation to a position sufficiently far from P, and which produces all such motions if they exist. The algorithm runs in time O(t(n)) where t(n) is the time needed to triangulate an n-sided polygon. Since Tarjan and Van Wyk have recently shown that t(n)=O(n log log n) this improves the previous best result for this problem which was O(n log n) even after triangulation.

Original languageEnglish (US)
Pages (from-to)265-278
Number of pages14
JournalDiscrete & Computational Geometry
Volume4
Issue number1
DOIs
StatePublished - Dec 1989

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'On separating two simple polygons by a single translation'. Together they form a unique fingerprint.

  • Cite this