.png){kind=icon}
返回
Computing roadmaps in unbounded smooth real algebraic sets II: Algorithm and complexity
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jsc.2025.102532.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
对于一个由有理数域Q上的多项式定义的代数集V，其规划图是一条包含在V中的代数曲线，且该曲线与V在Rⁿ中的所有连通分量的交集是连通的。这些由Canny引入的对象可用于回答关于V与Rⁿ交集的连通性查询，前提是它们需要包含V的有限查询点集P；在这种情况下，我们称该规划图与(V, P)相关联。在本文中，我们将先前证明的连通性结果实现为有效算法，以设计一种蒙特卡洛算法，该算法在输入(i)定义V的有限多项式序列（并满足某些正则性假设）和(ii)V中有限查询点集P的代数表示后，计算(V, P)的规划图。该算法推广了最后两位作者引入的几乎最优算法，通过取消了V实迹的界假设。我们算法的输出规模和运行时间均为(nD)n log d的多项式，其中D是输入方程的最大次数，d是V的维数。据我们所知，此前处理此类集合的最佳算法的输出规模和运行时间分别为(n log nD)n log n和(n log nD)n log² n。© 2025 Elsevier Ltd. All rights are reserved, including those for text and data mining, AI training, and similar technologies.
Keyword:
Computational real algebraic geometry
Real algebraic sets
Critical points
Roadmaps
Algorithm
Complexity
期刊
J
IF:
1.1
论文数:
38
被引数:
0
机构
引用论文
Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers通过提升纤维计算代数闭集的等维分解
.png){kind=icon}
PREAI
分享收藏Bit complexity for computing one point in each connected component of a smooth real algebraic set计算光滑实代数集的每个连通分量中一个点的位复杂度
PREAI
分享收藏A Baby Steps/Giant Steps Probabilistic Algorithm for Computing Roadmaps in Smooth Bounded Real Hypersurface一种适用于光滑有界实超曲面的婴儿步/巨人步概率算法，用于计算路径图
PREAI
分享收藏
分享收藏Computing roadmaps in unbounded smooth real algebraic sets I: Connectivity results计算无界光滑实代数集中的路线图 I：连通性结果
PREAI
分享收藏
查看更多内容