On the Complexity of the Plantinga–Vegter Algorithm
On the Complexity of the Plantinga–Vegter Algorithm
复制标题
论 PlantingaâVegter 算法的复杂性
DOI：
10.1007/s00454-022-00403-x
复制
发表时间：
2022
影响因子：
0.8
通讯作者：
Tonelli-Cueto, Josué
中科院分区：
文献类型：
--
作者：
Cucker, Felipe;Ergür, Alperen A.;Tonelli-Cueto, Josué
我们引入数值分析和高维概率工具，用于计算几何中基于细分的算法的精度控制和复杂性分析。我们将这些工具与精确计算的连续摊销框架相结合。我们在细分系列中的一个著名示例中使用这些工具：Plantinga 和 Vegter 提出的自适应细分算法。这种相当快的算法唯一现有的复杂性估计是其区间算术版本的指数最坏情况上限。我们通过考虑平均分析和平滑分析来超越最坏情况，并证明区间算术和 Plantinga-Vegter 算法的有限精度版本的多项式时间复杂度估计。
We introduce tools from numerical analysis and high dimensional probability for precision control and complexity analysis of subdivision-based algorithms in computational geometry. We combine these tools with the continuous amortization framework from exact computation. We use these tools on a well-known example from the subdivision family: the adaptive subdivision algorithm due to Plantinga and Vegter. The only existing complexity estimate on this rather fast algorithm was an exponential worst-case upper bound for its interval arithmetic version. We go beyond the worst-case by considering both average and smoothed analysis, and prove polynomial time complexity estimates for both interval arithmetic and finite-precision versions of the Plantinga–Vegter algorithm.
登录
查看更多内容
DOI：
10.1007/978-3-642-38896-5
发表时间：
2013-08
期刊：
--
影响因子：
--
作者：
Peter Bürgisser;F. Cucker
通讯作者：
Peter Bürgisser;F. Cucker
半代数几何中的条件和同调
DOI：
10.14279/depositonce-9453
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Josué Tonelli
通讯作者：
Josué Tonelli
影响因子：
3
作者：
Peter Bürgisser;F. Cucker;Josué Tonelli
通讯作者：
Josué Tonelli
通过复杂性分析分离真实方程组零点的有效细分算法
DOI：
10.1145/3326229.3326270
发表时间：
2019
期刊：
Proceedings of the 2019 on International Symposium on Symbolic and Algebraic Computation
影响因子：
--
作者：
Juan Xu;C. Yap
通讯作者：
C. Yap
DOI：
--
发表时间：
2015
期刊：
International Conference on Mathematical Aspects of Computer and Information Sciences
影响因子：
--
作者：
C. Jeannerod
通讯作者：
C. Jeannerod