Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane
Polytime algorithm for the shortest path in a homotopy class amidst semi-algebraic obstacles in the plane
复制标题
平面半代数障碍中同伦类最短路径的Polytime算法
DOI：
--
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
A. Slissenko
中科院分区：
文献类型：
--
作者：
D. Grigoriev;A. Slissenko
给定平面上的一组半代数障碍物和补的同一连通分支中的两个点，问题是在给定的同伦类中构造这些点之间的最短路径。这条路径是唯一的，并且具有某种规范形式。我们使用的同伦类的表示的方式，是作为一般的经典之一。它包括代表一个自由群的生成元，该自由群描述了同伦类的不相交割[GS 97]同胚射线。我们表明，给定这样一个系统的发电机和一个字表示同伦类，可以construct最短路径的这个类的时间多项式的大小字和大小的代表性的障碍和削减。同伦类也可以表示为一个路径，那么多项式的复杂性将取决于该路径的表示的大小。作为一个技术概念，我们引入一个特殊的切割系统，我们称之为极端的基础，证明是特别方便的算法目的。所考虑的问题是出于机器人运动规划和理论问题所产生的最短路径近似在更高的维度。
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 introduce 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.