Translating polygons in the plane

Jӧrg R. Sack, Godfried T. Toussaint

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

Abstract

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
Pages310-321
Number of pages12
ISBN (Print)9783540139126
DOIs
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

Other

Other2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985
CountryGermany
CitySaarbrucken
Period1/3/851/5/85

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this