The Complexity of an Adaptive Subdivision Method for Approximating Real Curves

Michael Burr 1 Shuhong Gao 1 Elias Tsigaridas 2
2 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria de Paris
Abstract : We present the first complexity analysis of the algorithm by Plantinga and Vegter for approximating real implicit curves and surfaces. This approximation algorithm certifies the topological correctness of the output using both subdivision and interval arithmetic. In practice, it has been seen to be quite efficient; our goal is to quantify this efficiency. We focus on the subdivision step (and not the approximation step) of the Plantinga and Vegter algorithm. We begin by extending the subdivision step to arbitrary dimensions. We provide a priori worst-case bounds on the complexity of this algorithm both in terms of the number of subregions constructed and the bit complexity for the construction. Then, we use continuous amortization to derive adaptive bounds on the complexity of the subdivided region. We also provide examples showing our bounds are tight.
Type de document :
Communication dans un congrès
ISSAC 2017 - International Symposium on Symbolic and Algebraic Computation, Jul 2017, Kaiserslautern, Germany. pp.8, 2017, 〈10.1145/3087604.3087654〉
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01528392
Contributeur : Elias Tsigaridas <>
Soumis le : mardi 30 mai 2017 - 23:24:45
Dernière modification le : jeudi 22 novembre 2018 - 15:05:49
Document(s) archivé(s) le : mercredi 6 septembre 2017 - 14:15:04

Fichier

PVPaper.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Michael Burr, Shuhong Gao, Elias Tsigaridas. The Complexity of an Adaptive Subdivision Method for Approximating Real Curves. ISSAC 2017 - International Symposium on Symbolic and Algebraic Computation, Jul 2017, Kaiserslautern, Germany. pp.8, 2017, 〈10.1145/3087604.3087654〉. 〈hal-01528392v2〉

Partager

Métriques

Consultations de la notice

210

Téléchargements de fichiers

65