Computing the first Betti number and the connected components of semi-algebraic sets
Computing the first Betti number and the connected components of semi-algebraic sets
复制标题
DOI：
10.1145/1060590.1060636
复制
发表时间：
2005-05
期刊：
影响因子：
--
通讯作者：
S. Basu;R. Pollack;Marie-Françoise Roy
中科院分区：
文献类型：
--
作者：
S. Basu;R. Pollack;Marie-Françoise Roy
在本文中，我们描述了第一单指数算法计算第一贝蒂数的一个给定的半代数集。我们还描述了用于获得任何给定的真实的代数或半代数集的半代数连接分量的半代数描述的算法。计算第0个贝蒂数和欧拉-庞加莱特征的单指数算法以前是已知的。除了第0个贝蒂数之外，没有已知的单指数算法来计算任何单个贝蒂数。
In this paper we describe the first singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. We also describe algorithms for obtaining semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set. Singly exponential algorithms for computing the zero-th Betti number, and the Euler-Poincaré characteristic, were known before. No singly exponential algorithm was known for computing any of the individual Betti numbers other than the zero-th one.