Separation of two monotone polygons in linear time

Godfried T. Toussaint, Hossam A. El Gindy

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)215-220
Number of pages6
Issue number4
StatePublished - Oct 1984

ASJC Scopus subject areas

  • Software
  • Control and Systems Engineering
  • General Mathematics
  • Computer Science Applications


Dive into the research topics of 'Separation of two monotone polygons in linear time'. Together they form a unique fingerprint.

Cite this