Session S34 - Symbolic and Numerical Computation with Polynomials

Wednesday, July 21, 18:00 ~ 18:30 UTC-3

Complexity of Plantinga-Vegter Algorithm

Alperen Ergur

UTSA, USA   -   This email address is being protected from spambots. You need JavaScript enabled to view it.

Plantinga-Vegter algorithm is a commonly used subdivision based method for meshing curves and surfaces. First rigorous complexity analysis of the method was provided by Burr, Gao, and Tsigaridas (https://doi.org/10.1016/j.jsc.2019.06.004) using the worst-case bit size complexity model. I'd like present beyond-worst-case analysis point of view on the complexity of Plantinga-Vegter algorithm using techniques from complexity theory of numerical algorithms and high dimensional probability. The ideas and techniques introduced in the talk are somewhat general and could be applied to a more broad family of symbolic-numeric algorithms.

Joint work with Felipe Cucker ( City University of Hong Kong) and Josue Tonelli-Cueto (Inria Paris & IMJ-PRG).

View abstract PDF