Translating polygons in the plane

Jӧrg R. Sack; Godfried T. Toussaint

doi:10.1007/BFb0024019

Translating polygons in the plane

Jӧrg R. Sack, Godfried T. Toussaint

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

Let P = (p₁,..,p_n) and Q = (q_l,..,q_m) 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 language	English (US)
Title of host publication	STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science
Editors	K. Mehlhorn
Publisher	Springer Verlag
Pages	310-321
Number of pages	12
ISBN (Print)	9783540139126
DOIs	https://doi.org/10.1007/BFb0024019
State	Published - 1985
Event	2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 - Saarbrucken, Germany Duration: Jan 3 1985 → Jan 5 1985

Publication series

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

Other

Other	2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985
Country/Territory	Germany
City	Saarbrucken
Period	1/3/85 → 1/5/85

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/BFb0024019

Cite this

Sack, J. R., & Toussaint, G. T. (1985). Translating polygons in the plane. In K. Mehlhorn (Ed.), STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science (pp. 310-321). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 182 LNCS). Springer Verlag. https://doi.org/10.1007/BFb0024019

Translating polygons in the plane. / Sack, Jӧrg R.; Toussaint, Godfried T.
STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science. ed. / K. Mehlhorn. Springer Verlag, 1985. p. 310-321 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 182 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Sack, JR & Toussaint, GT 1985, Translating polygons in the plane. in K Mehlhorn (ed.), STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 182 LNCS, Springer Verlag, pp. 310-321, 2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985, Saarbrucken, Germany, 1/3/85. https://doi.org/10.1007/BFb0024019

@inproceedings{8613a72d794e47f1bb41c6c6080f8c52,

title = "Translating polygons in the plane",

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.",

author = "Sack, {Jӧrg R.} and Toussaint, {Godfried T.}",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1985. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 2nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 1985 ; Conference date: 03-01-1985 Through 05-01-1985",

year = "1985",

doi = "10.1007/BFb0024019",

language = "English (US)",

isbn = "9783540139126",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "310--321",

editor = "K. Mehlhorn",

booktitle = "STACS 85 - 2nd Annual Symposium on Theoretical Aspects of Computer Science",

}

TY - GEN

T1 - Translating polygons in the plane

AU - Sack, Jӧrg R.

AU - Toussaint, Godfried T.

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 -

Translating polygons in the plane

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this