On the Complexity of the Plantinga-Vegter Algorithm

Felipe Cucker (1) , Alperen A. Ergür (2) , Josué Tonelli-Cueto (3, 4)

1 CUHK - City University of Hong Kong [Hong Kong]
2 Computer Science Department - Carnegie Mellon University
3 OURAGAN - OUtils de Résolution Algébriques pour la Géométrie et ses ApplicatioNs
4 IMJ-PRG (UMR_7586) - Institut de Mathématiques de Jussieu - Paris Rive Gauche

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.

Mots clés: Complexity; Subdivision methods; Plantinga-Vegter algorithm

Domaines: Géométrie algorithmique [cs.CG]; Analyse numérique [math.NA]

Felipe Cucker, Alperen A. Ergür, Josué Tonelli-Cueto. On the Complexity of the Plantinga-Vegter Algorithm. Discrete and Computational Geometry, 2022, ⟨10.1007/s00454-022-00403-x⟩. ⟨hal-02552018⟩