Separation of two monotone polygons in linear time

Abstract

SUMMARY Let P= ( p 1 , p 2 , …, p n ) and Q= (q 1 , q 2 , …, q m ) 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: , . 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.