Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Josué Tonelli-Cueto <>
Submitted on : Tuesday, December 22, 2020 - 11:06:59 PM
Last modification on : Wednesday, June 2, 2021 - 4:27:20 PM


Files produced by the author(s)


  • HAL Id : hal-02552018, version 1
  • ARXIV : 2004.06879


Felipe Cucker, Alperen A. Ergür, Josué Tonelli-Cueto. On the Complexity of the Plantinga-Vegter Algorithm. 2020. ⟨hal-02552018⟩



Record views


Files downloads