Translating polygons in the plane

Jӧrg R. Sack, Godfried T. Toussaint

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Let P = (p1,..,pn) and Q = (ql,..,qm) be two simple polygons with nonintersecting interiors in the plane specified by their cartesian coordinates in order. Given a direction d we can ask whether P can be translated an arbitrary distance in direction d without colliding with Q. It has been shown that this problem can be solved in time proportional to the number of vertices in P and Q. Here we present a new and efficient algorithm for determining all directions in which such movement is possible. In designing this algorithm a partitioning technique is developed which might find applications when solving other geometric problems. The algorithm utilizes several tools and concepts (e.g. convex hulls, point-location, weakly edge-visible polygons) from the area of computational geometry.

Original languageEnglish (US)
Title of host publicationSTACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science
EditorsK. Mehlhorn
PublisherSpringer Verlag
Number of pages12
ISBN (Print)9783540139126
StatePublished - 1985
Event2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 - Saarbrucken, Germany
Duration: Jan 3 1985Jan 5 1985

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume182 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Translating polygons in the plane'. Together they form a unique fingerprint.

Cite this