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

维普资讯 doc.guandang.net 第2 1卷第 1 O期

计

算

机

学

报

Vo 1 .2 1 No .1 0 0c t . 19 9 8

l 9 9 8年 1 0月

CHI NES E J . C OM P U TE RS

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

洪炳熔 (= ) l、 (哈尔滨工业大学计算机科学与工程系哈尔滨 1 5 0 0 0 1 )

摘

要

本文对由一组线性不等式围成的凸空间进行了深入的研究.对于空间中的一个固定的向

量，我们讨论了这一向量与这组线性不等式相应超平面和这一向量的关系，给出了三个定理 .并以此为基础，提出了一个判定由一组线性不等式围成的凸空间是否为空的一个快速算法称为向量定

位算法.根据这一算法可以给出线性规划中求解初始可行解的算法以及给出机器人路径规划中的碰撞检测算法. ~~~~

关键词

线性约束 ',凸空间，线性规划. __ _ _一 _,_一、 -_‘一

凸

分类号：TP 3 0 1

A FAS T ALGoRI TH M To DETERM I NE W H ETH ER Co NVEX REGI oNS BoUN DED BY M ULTI PLE LI NEAR

CoNSTRAI NTS ARE EM PTY REN S h i—— J u n HONG Bi n g—— Ro n g ( D e p a r t me n t o f C o m p u t e r S c i e n c e a n d E n g i n e e r i n g Ha r b i n I n s t i t u t e f o T e c h n o l o g y, Ha r b i n 1 5 0 0 0 1 )

Ab s t r a c t I n t h i s p a p e r,a d e e p r e s e a r c h o n t h e c o n v e x r e g i o n M b o u n d e d b y mu l—

t i p l e l i n e a r c o n s t r a i n t s,口| r

b ,i=== 1, 2,…, ,i s d o n e . Gi v e n a f i x e d v e c t o r,

t h e r e l a t i on b e t we e n t he ve c t or a nd t he h

y pe r p l an e s f o r me d b y t h e l i n e a r c on—

s t r a i n t s i s d i s c u s s e d . Th i s p a p e r d e f i n e s I 1, I 2, I 3 t o b e t h e s e t o f t h e s u b s c r i p t s o f l i n e a r c on s t r a i nt s t ha t t he s c a l a r pr o duc t of a n d t h e n or m v e c t or o f t h e hy p e r p l a ne o f t he c o r r e s p o ndi ng l i n e a r c on s t r a i nt i s gr e a t e r t ha n,e qu a l t o,or l e s s t h a n 0

r e s p e c t i v e l y .Th r e e t h e o r e ms a r e g i v e n .Th e o r e m 1:I f I 1一 o r I 3一，I 2一声，t h e n ≠ .Th e o r e m 2:I f o n e a n d o n l y o n e s e t o f I 1 a n d I 3 a r e e mp t y, b u t I z≠声，t h e n

≠j 5 i f a n d o n l y i f{ z I口 ≤b ,i∈I 2}≠ .Th e o r e m 3: I f M≠,I 1≠,I 3≠j 5, t h e n t he r e i s a s ub s c r i pt i 0∈ I1,s uc h t ha t ai 1 3 2]十口i 0 2 X2十…十口 i o n X 。

一 . r二毫

6 。i s n ot r e—

dun d a nt,t ha t i s un r e mo v a bl e i n t he d e c i s i on whe t he r M i s e mp t y. The r e i s a s ub— s c r i pt i 1∈I 3,s uc h t h a t af l 1 1十口/ 2 . 7 2 2十…十口i z 1 l n

i s n o t r e du nd a n t Ba . s e d on t he

本文 1 9 9 7— 0 7— 2 9收到，修改文 1 9 9 8— 0 4— 1 4收到.本课题得到国家自然

科学基金的资助.任世军，男， 1 9 6 2年生，博士研究生，副教授，现在从事人工智能、机器人路径规划、图论的研究，洪炳熔，男， 1 9 3 7年生，博士生导师，现在从事人工智 能、智能机器人、软件可靠性的研究.