刻画排列的连通分支

高犇

(太原理工大学数学学院,山西 太原 030024)

刻画排列的连通分支

高犇

(太原理工大学数学学院,山西 太原 030024)

应用柱代数分解算法和简化的胞腔相邻算法,得到一个刻画R3中由n个紧半代数集所组成排列连通分支的算法.

连通分支;紧半代数集;柱代数分解;胞腔相邻

1 引言

在固定维数欧几里得空间中几何对象的排列是计算几何和计算机修复几何设计中的基本对象[1].通常假定在这样一个排列中每个对象有个简单的描述,例如,它们是由固定次数的一些多项式所定义的半代数集.在三维空间中,二次曲面所形成的排列是特别重要的,因为它们被广泛的应用于CAD/CAM,计算机图表,机器人学[2]以及计算物理学[3-4]等相当多的学科中.因此,在R3中,计算和刻画紧半代数集所形成排列的连通分支是很必要的.

在计算半代数集所形成排列拓扑性质的许多算法中包含一个基本的组成部分,即柱代数分解算法[5],柱代数分解算法能把一个给定的半代数集分解成一些拓扑胞腔.从而可以计算一个半代数集的三角剖分[6],从这个三角剖分可以计算半代数集的连通分支,同调群等.但做柱代数分解时有一个缺点,即要使用迭代投影(即在柱代数分解的过程中每一步维数要减少1),并且多项式的数目在每一步过程中都会平方一次.因此,柱代数分解算法的复杂度是双指数的,这样在大多数情况下使得计算排列拓扑信息是不实际的.然而,对于低维的一些重要问题使用柱代数分解算法还是很有效的.

从柱代数分解算法中,能够获得胞腔相邻[7-8]的重要信息.非正式地讲,在Rn(n≥1)中,两个不相交的胞腔如果相互接触,则这两个胞腔是相邻的;正式的讲,如果两个胞腔的并是连通的,则这两个胞腔是相邻的.相邻信息是关于柱代数分解一些应用中的必要组成部分.例如,对于n=2和n=3,一个柱形分解构造算法已经被改进,可以使用相邻信息去规避原始算法[9]的某些时间耗散的步骤.Schwartz和Sharir应用胞腔相邻去研究运动问题[10],同样地, Arnon和McCallum在其算法中去求一条实代数曲线的拓扑类型[11].

本文中,应用柱代数分解算法和简化的胞腔相邻算法,得到一个刻画中由n个紧半代数集所组成排列中连通分支的算法.这个算法没有使用三角剖分.代替地,计算局部柱代数分解.在算法第2步,仅仅计算了部分胞腔相邻信息,并没有使用所有的胞腔相邻信息.本文的胞腔相邻算法比文献[7-8]中在平面和中求胞腔相邻的算法有所简化.并且为了刻画连通分支,本文中这些胞腔相邻算法的输入是(i=2,3)中的两个柱形区域或一个柱代数分解,而且在平面中没有退化的0-胞腔(参看文献[8]中定义).更多的,本文中胞腔相邻算法的过程比在文献[7-8]中算法的过程有所改进.

本文其它部分内容如下,第1节论述关于柱代数分解算法的预备知识.第2节论述平面和中的简化胞腔相邻算法.第3节提出一个在中刻画n个紧半代数集所组成排列中连通分支的算法.第4节对本文进行总结并对将来的工作提出一些想法.

2 柱代数分解算法的预备知识

本小节中,先介绍柱代数分解算法.对于柱代数分解更详细的内容请看文献[5-6,12-13].

输入有限多项式集

输出的F-符号不变柱代数分解及其代表系.

(1)如果n=1,求出多项式集F的各个多项式的所有实根r1

求出∏(F)在Γ′上的实根函数

(3)由此得到F-符号不变柱代数分解和它的代表系:

定义 2.1给定上的一个多项式有限集合Ω,中的一个子集S称为Ω-不变的,如果Ω中每个多项式P在S上是不变号的.如果关于的一个柱代数分解中的每个胞腔都是Ω-不变的,那么这个柱代数分解称为适应于Ω.

下面做对适应于单位球面的柱代数分解.

从柱代数分解算法中需要获得关于胞腔相邻[7-8]的重要信息.换言之,对某个柱代数分解中的两个胞腔,需要知道一个胞腔的闭包是否与另一个相交.例如,以上例子中,点(1,0,0)所对应的胞腔相邻于胞腔

在第2节中将要给出关于胞腔相邻更多的细节.

图1 适应于单位球面的柱代数分解

3 胞腔相邻

3.1 预备知识

对于适应于多项式所组成一个有限集合Ω的一个柱代数分解,为了描述获得所需胞腔相邻信息的方法,需要下面的内容.

更多地,可以直观地对胞腔进行如下标记.

对于R上的一个胞腔标记为Ci,当这个胞腔在一维数轴上从左到右数时为第i个胞腔.

更多地,定义关于柱代数分解中的i-胞腔,(0≤i≤3)是指i-维胞腔.在一个柱代数分解中一个l-胞腔和一个k-胞腔的相邻定义为{l,k}-相邻.

C2代表点 −1, C3代表集合 {x|−1

C2,1与C2,2为inter-stack胞腔相邻,C2,2与C3,2为intra-stack胞腔相邻;C2,2,2与C3,2,2为{0,1}-相邻.

在本文中,仅考虑紧半代数集Si,等价地,

deg(Pi,j(x,y,z))=2,并且,∗∈{≤,=}.下面的内容将要给出,在和中,适合于这种情况的柱代数分解中胞腔相邻算法.由于在文献[7-8]中主要算法结果的正确性,不难推出本文中关于胞腔相邻算法的正确性是显然的.具体详情请看文献[7-8].

在每一个柱形区域中,通过从下向上标记胞腔可以得到这个柱形区域中所有的 intrastack相邻信息.例如,胞腔Ci,j相邻于胞腔Ci,j+1.因此,为了得到关于的一个柱代数分解中的胞腔相邻信息,主要是确定inter-stack相邻信息.在R2中,通过利用{0,1}-inter-stack相邻信息和intra-stack相邻信息,就能确定关于R2的一个柱代数分解中所有其它胞腔相邻的信息.例如,假定Ci,j是一个 2-胞腔,包含在以 1-胞腔 Ci为基础的柱形区域中,并且下面和上面分别被两个 1-胞腔 Ci,j−1和 Ci,j+1所界定,其中 Ci,j−1和 Ci,j+1分别相邻于 0-胞腔 Ci−1,k1和 0-胞腔 Ci−1,k2(k1≤k2),并且这两个0-胞腔包含在以 0-胞腔 Ci−1为基础的柱形区域中,那么,Ci,j相邻于这个柱形区域中介于胞腔Ci−1,k1和胞腔Ci−1,k2之间所有的胞腔,并且在这个柱形区域中仅仅与这些胞腔相邻.因此,只要得到中的{0,1}-inter-stack相邻信息,就能获得所有的inter-stack相邻信息.下面的算法给出了关于的一个柱代数分解中{0,1}-inter-stack相邻信息的描述.

算法 1

输入关于的一个柱代数分解中分别以0-胞腔c0=(α,0)和1-胞腔

为基础的2个柱形区域A和B,其中c0相邻于c1.

输出L1是柱形区域A和B之间所有{0,1}-inter-stack相邻信息的表.

1.令L1←ϕ.求柱形区域A中的0-胞腔

得到

2.如果有一个 sj,0≤j≤m,使得 y=yj与柱形区域 B中的某个 1-胞腔相交,令u←直到y=yj与以{(x,y)|α

3.令柱形区域A中的±∞-截面分别相邻于柱形区域B中的±∞-截面.在柱形区域B中从下向上求1-胞腔,···,(l≥0).对j=1,···,m做以下3步:

3.1.令n←0和nj←是x=u与柱形区域B中介于y=yj−1和y=yj之间1-胞腔的相交数目.

3.2.在L1中,柱形区域A中的0-胞腔相邻于柱形区域B中的1-胞腔,···.

3.3.令n←n+nj.

如果c0在c1的右边,重复算法1.

算法 2

输入关于的一个柱代数分解.

输出I是这个柱代数分解中所有胞腔的指标表.L是这个柱代数分解中所有胞腔相邻信息的表.

1.令I←ϕ.令L←ϕ.构造柱代数分解(平面)所诱导的柱代数分解(线)中的胞腔指标Ci,(1≤i≤2n+1,n≥0).对i=1,···,2n+1做以下2步:

2.2.记录这个柱形区域中intra-stack相邻信息到L中.

2.对i=1,···,2n,利用算法1,输入分别以Ci和Ci+1为基础的2个柱形区域,然后添加输出L1到L中(注意,由算法1所输出的胞腔相邻信息中的胞腔必须首先转换成关于的柱代数分解中所对应的胞腔指标).

3.正如第2.2节中第2段所述,使用目前L中的信息可以推出关于的这个柱代数分解中其它inter-stack相邻信息,然后添加到L中.

算法 3

输入关于的一个柱代数分解中的2个柱形区域A和B,并且A和B分别是以中的一个0-胞腔c0=(α,β),α,β∈R和一个1-胞腔c1为基础的柱形区域,其中c0相邻于c1. p=(ρ,σ),(ρ,σ∈是c1中的一个样本点.F(x,y,z)∈[x,y,z]使得H(z)=F(α,β,z)的根定义柱形区域A,F(ρ,σ,z)的根定义柱形区域B.G(x,y)∈(x,y)关于x或y或两个的次数是正的.c1和c0包含在Zero(G(x,y))(即G(x,y)实根的集合)中.

输出L是柱形区域A和B之间所有的{0,1}-inter-stack相邻信息表.

1.如果 degy(G)>0,然后令 P(x,z)← Resy(G,F)(F和 G关于 y的结式),否则如果degx(G)>0,然后令P(y,z)←Resx(G,F)(F和G关于x的结式).不失一般性,从现在开始假定G关于y的次数是正的,并且c1在c0的右边,因此在这步计算P(x,z).

2.令 J=Proj({P(x,z)}).求 J中元素的实根,得到 b∈使得 P定义 2个分别以 (α,0)和 {(x,z)|α

3.1.缩小关于这个根的孤立区间直到这个区间只与P(ˆb,z)的一个根的唯一孤立区间相交,获得s1唯一的投影1-胞腔t1;

3.2.令 t0是柱形区域 A′中 t1唯一的边界 0-胞腔 (从 L1中获得),然后缩小关于P(α,z)和H(z)的根的孤立区间直到对应于t0的关于P(α,z)的根的孤立区间与H(z)的一个根的唯一孤立区间相交,即求出了柱形区域A中s1的边界0-胞腔.

算法 4

输入关于的一个柱代数分解中的2个柱形区域A和B,并且A和B分别是以中的一个1-胞腔c1和一个2-胞腔c2为基础的柱形区域,其中c1相邻于c2.

输出L是柱形区域A和B之间所有的{1,2}-inter-stack相邻信息表.

1.如果关于R的诱导柱代数分解中存在一个1-胞腔

使得c1和c2包含在以c′为基础的柱形区域中,并且c2在c1的上面(下面).令是c′中的样本点,计算

得到关于R2的一个柱代数分解中的2个柱形区域A′和B′,并且这2个柱形区域分别以0-胞腔和1-胞腔

为基础.利用算法1,输入A′和B′,得到输出L′,然后添加L′到L.

否则2.如果关于R的诱导柱代数分解中存在一个0-胞腔c0=(α1,0),(α1∈)使得c1包含在以c0为基础的柱形区域中,并且c2在c1的右面(左面).令(α1,β),(β∈)是c1中的样本点,计算{(x,y)|α1

如果c0和c2是关于的一个柱代数分解中的一个0-胞腔和一个2-胞腔,并且c0相邻于c2,那么恰好在关于的这个柱代数分解中存在2个1-胞腔使得同时相邻于c0和c2.

算法 5

输入关于的一个柱代数分解中的2个柱形区域A和B,并且A和B分别是以中的一个0-胞腔c0=(α,β),α,β∈和一个2-胞腔c2为基础的柱形区域,其中c0相邻于c2.

输出L是柱形区域A和B之间所有的{0,2}-inter-stack相邻信息表.

1.选择一个1-胞腔c1,使得c1同时相邻于c0和c2.

2.对柱形区域B中的每个2-胞腔s2,利用算法4,从以c1为基础的柱形区域中得到s2的边界1-胞腔t1.

3.利用算法3,从柱形区域A中得到t1的边界0-胞腔t0.那么对于t1而言,{t0,s2}是柱形区域A和B之间唯一的{0,2}-inter-stack相邻,添加它到L中.

算法 6

输入关于的一个柱代数分解.

输出I是这个柱代数分解中所有胞腔的指标表.L是这个柱代数分解中所有胞腔相邻信息的表.

1.令 I←ϕ.令 L←ϕ.利用算法 2,输入关于这个柱代数分解 ()诱导的柱代数分解(平面上),获得关于诱导柱代数分解(平面上)的输出I′和L′.对每个胞腔Ci,j做以下2步:

1.2.记录这个柱形区域中的intra-stack相邻信息到L中.

2.对L′中的每对相邻胞腔{c,d},根据c和d的维数,选择以下3种情况中的一种,在这个柱代数分解(R3)中求以这2个相邻胞腔为基础的柱形区域之间的某些inter-stack相邻信息.

2.1.令 c0=(α,β),α,β∈和 c1是一对相邻胞腔.令关于的这个柱代数分解中以 c0和 c1为基础的 2个柱形区域分别是 A和 B.令 p=(ρ,σ),ρ,σ∈是 c1中的样本点,H(z)=F(α,β,z)的根定义柱形区域A,F(ρ,σ,z)的根定义柱形区域B.令c0和c1包含在Zero(G(x,y))中.利用算法3,输入c0,c1,A,B,p,H(z),F(α,β,z)和G(x,y),得到输出L∗.注意,在修改L∗中元素的指标后,添加它们到L中.

2.2.令c1和c2是一对相邻胞腔.令关于的这个柱代数分解中以c1和c2为基础的2个柱形区域分别是A和B.利用算法4,输入A,B,c1和c2,得到输出L∗.注意,在修改L∗中元素的指标后,添加它们到L中.

2.3.令c0和c2是一对相邻胞腔.令关于的这个柱代数分解中以c0和c2为基础的2个柱形区域分别是A和B.利用算法5,输入A,B,c0和c2,得到输出L∗.添加L∗中的元素到L中.

3.使用L中现有的内容推出关于这个柱代数分解其它的inter-stack相邻信息.添加它们到L中.

3 刻画连通分支

这些胞腔包含在S中,并且在这个柱代数分解中只有这些胞腔包含在S中.更多地,C2,2,2相邻于,,和;相邻于,和;相邻于, C3,3,4和C4,2,2;C4,2,2相邻于C3,3,2和C3,3,4.所以S是半代数连通的,即在S中仅有一个连通分支.这个连通分支能被刻画为:

下面给出刻画连通分支的算法.

算法 7

输入中 n个紧半代数集的并集 S,其中每个集合 Si,(1≤i≤n)由有限个集合的并集所定义,其中

输出S中连通分支的刻画D.

1.对每个

做以下4步:

1.1.计算适应于集合{Si,1,···,Si,ki}的一个柱代数分解.

1.2.利用算法6,输入这个柱代数分解,得关于此柱代数分解中所有胞腔相邻信息的表.

1.3.确定这个柱代数分解中所有包含于Si的胞腔.

1.4.刻画Si中所有的连通分支{,,···,}.

2.对{S11,1,S11,2,···,}和{,,···,},做以下几步:

2.1.令

2.1.1.搜索 {S1,α1,···,S1,αw}⊆ {S1,p1{,···,S1,pe},满足 S1,α1∩[ξ,η]×?∅,···, S1,αw∩[ξ,η]×?∅.{S2,β1,···,S2,βv}⊆S2,q1,···,S2,qf},满足

2.1.2.求适应于集合{S1,α1,···,S1,αw,S2,β1,···,S2,βv}的一个柱代数分解.

2.1.3.利用算法6,输入这个柱代数分解,得关于这个柱代数分解中所有包含于[ξ,η]×的胞腔相邻信息的表.

2.2.由第 2.1步中的内容,得到 S1∪S2中所有连通分支 {,,···,}的刻画.令S1←S1∪S2.

3.对{S12,1,S12,2,···,}和{S31,1,S31,2,···,},重复第 2步,得到 S1∪S3中所有连通分支{,,···,}的刻画.令S1←S1∪S3.

4.重复第3步,得到S1∪Sr,(3≤r≤n)中所有连通分支{,,···,}的刻画.添加S=S1∪Sn中所有连通分支{,,···,}的刻画到D中.

算法 7的正确性由柱代数分解算法和前面胞腔相邻算法的正确性所保证.注意,在算法7中的每1步,通过计算适应于在R[x1,x2,x3]中一个有限多项式集的柱代数分解和使用算法6,能确定所有包含于上面这些多项式所定义集合中胞腔相邻的信息.使用这些胞腔相邻信息,多项式所定义集合能作为有限数目半代数连通分支不相交的并,而且这些连通分支能被刻画.通过迭代,能获得排列中所有的连通分支.而且算法7能在有限步内结束.更多地,对空间中给定的一个点,能够判断这个点是否包含于某个连通分支.这个方法能被应用于碰撞检测,机器人学等领域.

4 结论

参考文献

[1]Halperin D,Sharir M.Arrangements and Their Applications in Robotics:Recent Developments.In WAFR: Proceedings of the Workshop on Algorithmic Foundations of Robotics[M].Natick:Springer-Star,1995.

[2]Rimon E,Boyd S.Obstacle collision detection using best ellipsoid f i t[J].Journal of Intelligent and Robotic Systems,1997(2):105-126.

[3]Lin X,Ng T T.Contact detection algorithms for three-dimensional ellipsoids in discrete element method[J]. International Journal for Numerical and Analytical Methods in Geomechanics,1995,19(9):653-659.

[4]Perram J W,Rasmussen J,Praestgaard E,et al.Ellipsoid contact potential:Theory and relation to overlap potentials[J].Physical Review E,1996(6):6565-6572.

[5]Collins G E.Quantif i er elimination for real closed f i elds by cylindrical algebraic decomposition[J].Automata theory and formal languages,1975,33(6):134-183.

[6]Basu S,Pollack R,Roy M F.Algorithms in Real Algebraic Geometry[M].Berlin:Springer-Verlag,2003.

[7]Arnon D S,Collins G E,McCallum S.Cylindrical algebraic decomposition,II:An adjacency algorithm for the plane[J].SIAM J.Comput.,1984,13(4):878-889.

[8]Arnon D S,Collins G E,McCallum S.An adjacency algorithm for cylindrical algebraic decompositions of three-dimensional space[J].J.Symbolic Comput.,1988(5):163-187.

[9]Arnon D S.Algorithms for the Geometry of Semi-Algebraic Sets[M].Madison:Springer-Vienna,1981.

[10]Schwartz J,Sharir M.On the piano movers′problem II.General techniques for computing topological properties of real algebraic manifolds[J].Advances in Applied Mathematics,1983(4):298-351.

[11]Arnon D S,McCallum S.A polynomial-time algorithm for the topological type of a real algebraic curveextended abstract[J].Rocky Mountain J.Math.,1984(4):849-852.

[12]Arnon D S,Collins G E,McCallum S.Cylindrical algebraic decomposition,I:The basic algorithm[J].SIAM J.Comput.,1984,13(4):865-877.

[13]Chen Yufu.Lectures on Computer Algebra[M].Beijing:Higher education Press,2009.

Description of the connected components of arrangements

Gao Ben
(College of Mathematics,Taiyuan University of Technology,Taiyuan 030024,China)

We give an algorithm for computing connected components of arrangements of n compact semialgebraic sets inby using the methods of cylindrical algebraic decomposition and simplif i ed cell adjacencies.

connected component,compact semi-algebraic set,cylindrical algebraic decomposition, cell adjacency

O187.1

A

1008-5513(2014)02-0154-12

10.3969/j.issn.1008-5513.2014.02.006

2013-01-21.

山西省回国留学人员科研资助项目(2013-045);太原理工大学校青年项目基金(2013Z026).

高犇(1985-),博士,讲师,研究方向：计算机代数.

2010 MSC:08B8