Colloquium by Josué Tonelli-Cueto (Technische Universität Berlin): Condition meets Computational Geometry: The Plantinga-Vegter algorithm case

Apr 15, 2019 | 04:00 PM s.t.

The Plantinga-Vegter algorithm is a subdivision algorithm that produces an isotopic approximation of implicit smooth curves in the plane (and also of surfaces in the three dimensional space). Despite remarkable practical success of the algorithm, little was known about its complexity. The only existing complexity analysis due to Burr, Gao and Tsigaridas provides worst-case bounds that are exponential both in the degree and the bit size of the input polynomial. Despite being tight, this worst-case bound doesn't explain why the algorithm is efficient in practice.
In this talk, we show how condition numbers, combined with techniques from geometric functional analysis, help to solve this issue.
This is joint work with Alperen A. Ergür and Felipe Cucker.

Time & Location

Apr 15, 2019 | 04:00 PM s.t.

Freie Universität Berlin
Institut für Informatik
Takustr. 9
14195 Berlin
Room 005 (Ground Floor)

Freie Universität Berlin
Technische Universität Berlin
Humboldt-Universität zu Berlin
Deutsche Forschungsgemeinschaft (DFG)