论文标题
关于种植算法的复杂性
On the Complexity of the Plantinga-Vegter Algorithm
论文作者
论文摘要
我们从数值分析和高维概率中介绍了工具，以对基于细分的算法进行精确控制和复杂性分析。我们将这些工具与精确计算的连续摊销框架相结合。我们在细分家族的一个众所周知的例子上使用这些工具：由于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.
