On Critical Orientations in the Kedem-Sharir Motion Planning Algorithm for a Convex Polygon in the Plane.
Klara Kedem, Micha Sharir, Sivan Toledo · 1993
We discuss a technical problem arising in the motion planning algorithm of Kedem and Sharir [KS], and propose a way to overcome it without increasing the asymptotic complexity of the algorithm. 1 Introduction The paper "An efficient motion-planning algorithm for a convex polygonal object in two-dimensional polygonal space", by Kedem and Sharir [KS], studies the problem of planning a collision-free motion (including translation and rotation) for a convex polygonal body B, with k corners, amidst polygonal obstacles having n corners altogether. More specifically, the problem is stated as follows: given initial and final placements of B, determine whether there is an obstacle-avoiding motion from the initial placement to the final placement and, if so, plan such a motion. In what follows we assume some familiarity of the reader with the algorithm of [KS]. Nevertheless we will present a brief description of the technique, providing enough details to allow us to state the technical diff...