Efficient simplicial replacement of semialgebraic sets
Efficient simplicial replacement of semialgebraic sets
复制标题
半代数集的高效单纯替换
DOI：
10.1017/fms.2023.36
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Karisani, Negin
中科院分区：
文献类型：
--
作者：
Basu, Saugata;Karisani, Negin
设计一个具有单指数复杂度的算法来计算给定半代数集合的半代数三角剖分一直是算法半代数几何中的圣杯。更确切地说，给定一个半代数集的描述，用实数语言的一阶无量词公式，目标是输出一个单纯复形，其几何实现，是半代数同胚的S。在本文中，我们考虑这个问题的一个较弱的版本。我们证明了，对于任何，存在一个算法，作为输入的半代数子集的描述给出了一个量词免费的一阶公式在语言的reals和生产作为输出的单纯复形，其几何实现，是-等价于S。我们的算法的复杂性是有界的，其中s是出现在公式中的多项式的数量，和d上界他们的程度。对于固定的，这个界限是单指数的k。特别是，由于-等价意味着同伦群的维数是同构的S，我们得到一个减少（具有单指数复杂性）的问题计算的第一同伦群的S的组合问题计算的第一同伦群的有限单纯复杂的大小有界。
Designing an algorithm with a singly exponential complexity for computing semialgebraic triangulations of a given semialgebraic set has been a holy grail in algorithmic semialgebraic geometry. More precisely, given a description of a semialgebraic set by a first-order quantifier-free formula in the language of the reals, the goal is to output a simplicial complex , whose geometric realization, , is semialgebraically homeomorphic to S. In this paper, we consider a weaker version of this question. We prove that for any , there exists an algorithm which takes as input a description of a semialgebraic subset given by a quantifier-free first-order formula in the language of the reals and produces as output a simplicial complex , whose geometric realization, is -equivalent to S. The complexity of our algorithm is bounded by , where s is the number of polynomials appearing in the formula , and d a bound on their degrees. For fixed , this bound is singly exponential in k. In particular, since -equivalence implies that the homotopy groups up to dimension of are isomorphic to those of S, we obtain a reduction (having singly exponential complexity) of the problem of computing the first homotopy groups of S to the combinatorial problem of computing the first homotopy groups of a finite simplicial complex of size bounded by .
登录
查看更多内容
影响因子：
3
作者：
Peter Bürgisser;F. Cucker;Josué Tonelli
通讯作者：
Josué Tonelli
同胚问题的不解性 *
影响因子：
0.8
作者：
A. Markov;Champaign German;Rolf Herken
通讯作者：
Rolf Herken
计算半代数集的第一个贝蒂数
影响因子：
3
作者：
S. Basu;R. Pollack;Marie
通讯作者：
Marie
DOI：
10.1145/3275242
发表时间：
2018
期刊：
Journal of the ACM (JACM)
影响因子：
--
作者：
P. Bürgisser;F. Cucker;P. Lairez
通讯作者：
P. Lairez
影响因子：
3
作者：
Peter Bürgisser;F. Cucker;Josué Tonelli
通讯作者：
Josué Tonelli