Computing the First Betti Number of a Semi-Algebraic Set
Computing the First Betti Number of a Semi-Algebraic Set
复制标题
计算半代数集的第一个贝蒂数
DOI：
10.1007/s10208-007-9001-1
复制
发表时间：
2008
影响因子：
3
通讯作者：
Marie
中科院分区：
文献类型：
--
作者：
S. Basu;R. Pollack;Marie
摘要
在本文中，我们描述了一个单指数算法计算给定的半代数集的第一贝蒂数。计算第零个贝蒂数和欧拉-庞加莱特征的单指数算法以前是已知的。除了第0个贝蒂数之外，没有已知的单指数算法可以计算任何一个贝蒂数。因此，我们也得到算法计算半代数描述的半代数连接组件的任何给定的真实的代数或半代数集在单指数时间，这提高了以前发表的算法的复杂性，这个问题。
Abstract
In this paper we describe a singly exponential algorithm for computing the first Betti number of a given semi-algebraic set. Singly exponential algorithms for computing the zeroth 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 zeroth one. As a consequence we also obtain algorithms for computing semi-algebraic descriptions of the semi-algebraically connected components of any given real algebraic or semi-algebraic set in singly exponential time, which improves on the complexity of the previously published algorithms for this problem.