On the Complexity of the Plantinga-Vegter Algorithm
arXiv:2004.06879 · doi:10.1007/s00454-022-00403-x
Abstract
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.
32 pages, 1 figure. This paper supersedes our earlier conference paper (arXiv:1901.09234). 2nd version: Re-structuring of the paper and correction of typos
References in corpus (5)
- Computing the homology of basic semialgebraic sets in weak exponential time
- Computing the Homology of Semialgebraic Sets. II: General formulas
- Computing the Homology of Semialgebraic Sets I: Lax Formulas
- Probabilistic Condition Number Estimates For Real Polynomial Systems I: A Broader Family Of Distributions
- Plantinga-Vegter algorithm takes average polynomial time