Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane

Abstract

Given a set of semi-algebraic obstacles in the plane and two points in the same connected component of the complement, the problem is to construct the shortest path between these points in a given homotopy class. This path is unique and has some canonical form. We use the representation of homotopy classes in a way that is as general as the classical one. It consists in representing generators of a free group which describes the classes of homotopy by disjoint cuts GS97 homeomorphic to rays. We show that given such a system of generators and a word representing a homotopy class, one can contruct the shortest path of this class in time polynomial in the size of the word and in the size of the representation of the obstacles and the cuts. The homotopy class may also be represented by a path, then the polynomial complexity will depend on the size of the representation of this path. As a technical notion we i n troduce one particular system of cuts, which we call an extremity basis, that proves to be especially convenient for algorithmic purposes. The considered problem is motivated by robot motion planning and by theoretical questions arising in shortest path approximations in higher dimensions.