TY - GEN

T1 - Translating polygons in the plane

AU - Sack, Jӧrg R.

AU - Toussaint, Godfried T.

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1985.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1985

Y1 - 1985

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84934031999&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84934031999&partnerID=8YFLogxK

U2 - 10.1007/BFb0024019

DO - 10.1007/BFb0024019

M3 - Conference contribution

AN - SCOPUS:84934031999

SN - 9783540139126

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 310

EP - 321

BT - STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science

A2 - Mehlhorn, K.

PB - Springer Verlag

T2 - 2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985

Y2 - 3 January 1985 through 5 January 1985

ER -