On the Complexity of the Plantinga-Vegter Algorithm

Abstract

We introduce a general toolbox for precision control and complexity analysis of subdivision based algorithms in computational geometry. We showcase the toolbox on a well known example from this 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 smoothed analysis, and prove polynomial time complexity estimates for both interval arithmetic and finite precision versions of the Plantinga-Vegter algorithm. The employed toolbox is a blend of robust probabilistic techniques coming from geometric functional analysis with condition numbers and the continuous amortization paradigm introduced by Burr, Krahmer and Yap. We hope this combination of tools from different disciplines would prove useful for understanding complexity aspects of the broad family of subdivision based algorithms in computational geometry.