判定由线性不等式围成的凸空间是否为空的一个快速算法

A FAST ALGORITHM TO DETERMINE WHETHER CONVEX REGIONS BOUNDED BY MULTIPLE LINEAR CONSTRAINTS ARE EMPTY

本文对由一组线性不等式围成的凸空间进行了深入的研究．对于空间中的一个固定的向量，我们讨论了这一向量与这组线性不等式相应超平面和这一向量的关系，给出了三个定理．并以此为基础，提出了一个判定由一组统性不等式围成的凸空间是否为空的一个快速算法称为向量定位算法，根据这一算法可以给出线性规划中求解初始可行解的算法以及给出机器人路径规划中的碰撞检测算法．

In this paper, a deep research on the convex region M bounded by mul-tiple linear constraints, i=1, 2, n, is done. Given a fixed vector a,the relation between the vector and the hyper planes formed by the linear con-straints is discussed. This paper defines I1,I2,I3 to be the set of the subscripts oflinear constraints that the scalar product of a and the norm vector of the hyperplane of the corresponding linear constraint is greater than, equal to, or less than Orespectively. Three theorems are given. Theorem 1: If I1=φ orI3=φ, I2=φ, thenM≠φ. Theorem 2: If one and only one set of I1 and I3 are empty,but I2≠φ, thenM≠φif and only if Theorem 3: If M≠φ, I1≠φ, I3≠φ,then there is a subscript io I1, such that is not re-dundant, that is unremovable in the decision whether M is empty. There is a sub-script i1 I3, such that is not redundant. Based on theabove three theorems, this paper presents a fast algorithm to determine whetherthe convex regions bounded by multiple linear constraints are empty.