Separation of two monotone polygons in linear time

Godfried T. Toussaint; Hossam A. El Gindy

doi:10.1017/S0263574700008924

Separation of two monotone polygons in linear time

Godfried T. Toussaint, Hossam A. El Gindy

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Let P = (p₁, p₂, …, p_n) and Q = (q₁ q₂, …, q_m) be two simple polygons monotonic in directions θ and ϕ, respectively. It is shown that P and Q are separable with a single translation in at least one of the directions: θ + π/2, ϕ + π/2. Furthermore, a direction for carrying out such a 2 translation can be determined in O(m + n) time. This procedure is of use in solving the FIND-PATH problem in robotics.

Original language	English (US)
Pages (from-to)	215-220
Number of pages	6
Journal	Robotica
Volume	2
Issue number	4
DOIs	https://doi.org/10.1017/S0263574700008924
State	Published - Oct 1984

ASJC Scopus subject areas

Software
Control and Systems Engineering
General Mathematics
Computer Science Applications

Access to Document

10.1017/S0263574700008924

Cite this

@article{db815d80d6bf4165acd31ccab108afee,

title = "Separation of two monotone polygons in linear time",

abstract = "Let P = (p1, p2, …, pn) and Q = (q1 q2, …, qm) be two simple polygons monotonic in directions θ and ϕ, respectively. It is shown that P and Q are separable with a single translation in at least one of the directions: θ + π/2, ϕ + π/2. Furthermore, a direction for carrying out such a 2 translation can be determined in O(m + n) time. This procedure is of use in solving the FIND-PATH problem in robotics.",

author = "Toussaint, {Godfried T.} and {El Gindy}, {Hossam A.}",

year = "1984",

month = oct,

doi = "10.1017/S0263574700008924",

language = "English (US)",

volume = "2",

pages = "215--220",

journal = "Robotica",

issn = "0263-5747",

publisher = "Cambridge University Press",

number = "4",

}

TY - JOUR

T1 - Separation of two monotone polygons in linear time

AU - Toussaint, Godfried T.

AU - El Gindy, Hossam A.

PY - 1984/10

Y1 - 1984/10

N2 - Let P = (p1, p2, …, pn) and Q = (q1 q2, …, qm) be two simple polygons monotonic in directions θ and ϕ, respectively. It is shown that P and Q are separable with a single translation in at least one of the directions: θ + π/2, ϕ + π/2. Furthermore, a direction for carrying out such a 2 translation can be determined in O(m + n) time. This procedure is of use in solving the FIND-PATH problem in robotics.

AB - Let P = (p1, p2, …, pn) and Q = (q1 q2, …, qm) be two simple polygons monotonic in directions θ and ϕ, respectively. It is shown that P and Q are separable with a single translation in at least one of the directions: θ + π/2, ϕ + π/2. Furthermore, a direction for carrying out such a 2 translation can be determined in O(m + n) time. This procedure is of use in solving the FIND-PATH problem in robotics.

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

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

U2 - 10.1017/S0263574700008924

DO - 10.1017/S0263574700008924

M3 - Article

AN - SCOPUS:0021504531

SN - 0263-5747

VL - 2

SP - 215

EP - 220

JO - Robotica

JF - Robotica

IS - 4

ER -

Separation of two monotone polygons in linear time

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this