Separation of two monotone polygons in linear time

Godfried T. Toussainta1 and Hossam A. El Gindya1

a1 School of Computer Science, McGill University, 805 Sherbrooke Street West, Montreal, Quebec (Canada) H3A 2K6


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

(Received July 03 1984)