A LINEAR TIME ALGORITHM FOR FINDING THE CONVEX ROPES BETWEEN TWO VERTICES OF A SIMPLE POLYGON WITHOUT TRIANGULATION
Phan Thanh An, Hoang An Quoc, Md. Abdus Salam · 2008
The convex rope problem, posed by Peshkin and Sanderson in IEEE J. Robotics Automat, 2 (1986) pp. 53-58, is to find the counterclockwise and clockwise convex ropes starting at the vertex a and ending at the vertex b of a simple polygon, where a is on the boundary of the convex hull of the polygon and b is visible from infinity. In this paper, we present a linear time algorithm for solving this problem without resorting to a linear-time triangulation algorithm and without resorting to a convex hull algorithm for the polygon. The counterclockwise (clockwise, respectively) convex rope consists of two polylines obtained in a basic incremental strategy described in convex hull algorithms for the polylines forming the polygon from a to b.