A co-homology method for computing compact semi-algebraic sets
Received date: 2009-09-18
Online published: 2010-11-15
高犇 , 陈玉福 , 张智勇 . 计算紧半代数集的同调方法[J]. 中国科学院大学学报, 2010 , 27(6) : 838 -846 . DOI: 10.7523/j.issn.2095-6134.2010.6.016
We describe an algorithm for computing the zero-th and first Betti numbers of the union of compact semi-algebraic sets.The complexity of the algorithm is single exponential.
[1] Halperin D.Arrangements . Handbook of discrete and computational geometry,CRC Press Ser Discrete Math Appl,CRC,Boca Raton,FL,1997:389-412.
[2] Rimon E, Boyd S.Obstacle collision detection using best ellipsoid fit
[J].Journal of Intelligent and Robotic Systems,1997,18: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,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] Chazelle B, Edelsbrunner H,Guibas L J,et al.A singly-exponential stratification scheme for real semi-algebraic varieties and its applications
[J].Theoretical Computer Science,1991, 84:77-105.
[6] Edelsbrunner H.The union of balls and its dual shape
[J].Discrete Comput Geom,1995,13(3/4):415-440.
[7] 陈玉福.计算机代数讲义
[M].北京:高教出版社,2009.
[8] Collins G E.Quantifier elimination for real closed fields by cylindrical algebraic decomposition // Automata theory and formal languages, second GI Conf,Kaiserslautern,1975,134-183.Lecture Notes in Comput Sci, Springer,Berlin,1975,33.
[9] Basu S,Ollack R, Roy M-F.Algorithms in real algebraic geometry,Algorithms and Computation in Mathematics
[M].Berlin:Springer-Verlag,2003.
[10] 姜伯驹.同调论
[M].北京:北京大学出版社,2006.
[11] Basu S, Kettner M.Computing the Betti numbers of arrangements in practice //compuing Algebra in Scientific Computing(CASC 2005),LNCS 3718 of Springer- Verlag,2005:13-31.
[12] 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(1/2):163-187.
[13] Basu S,Ollack R,Roy M-F.Algorithms in real algebraic geometry,vol.10 of Algorithms and Computation in Mathematics
[M]. 2nd ed, Berlin: Springer-Verlag,2006.
[14] Basu S, Pollack R, Roy M-F. Computing the first Betti number and the connected components of semi-algebraic sets //Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing,2005.
/
| 〈 |
|
〉 |
