A Subdivision Approach to Planar Semi-algebraic Sets

Angelos Mantzaflaris 1 Bernard Mourrain 1
1 GALAAD - Geometry, algebra, algorithms
CRISAM - Inria Sophia Antipolis - Méditerranée , UNS - Université Nice Sophia Antipolis, CNRS - Centre National de la Recherche Scientifique : UMR6621
Abstract : Semi-algebraic sets occur naturally when dealing with implicit models and boolean operations between them. In this work we present an algorithm to efficiently and in a certified way compute the connected components of semi-algebraic sets given by intersection or union of conjunctions of bi-variate equalities and inequalities. For any given precision, this algorithm can also provide a polygonal and isotopic approximation of the exact set. The idea is to localize the boundary curves by subdividing the space and then deduce their shape within small enough cells using only boundary information. Then a systematic traversal of the boundary curve graph yields polygonal regions isotopic to the connected components of the semi-algebraic set. Space subdivision is supported by a kd-tree structure and localization is done using Bernstein representation. We conclude by demonstrating our C++ implementation in the CAS Mathemagix.
Type de document :
Communication dans un congrès
Bernard Mourrain, Scott Schaefer, Guoliang Xu. 6th International Conference, GMP, Jun 2010, Castro Urdiales, Spain. Springer Berlin / Heidelberg, 6130, pp.104-123, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13411-1〉
Liste complète des métadonnées

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


https://hal.inria.fr/inria-00463491
Contributeur : Angelos Mantzaflaris <>
Soumis le : samedi 30 octobre 2010 - 16:40:49
Dernière modification le : jeudi 11 janvier 2018 - 16:14:50
Document(s) archivé(s) le : vendredi 2 décembre 2016 - 09:03:06

Fichiers

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

Identifiants

Citation

Angelos Mantzaflaris, Bernard Mourrain. A Subdivision Approach to Planar Semi-algebraic Sets. Bernard Mourrain, Scott Schaefer, Guoliang Xu. 6th International Conference, GMP, Jun 2010, Castro Urdiales, Spain. Springer Berlin / Heidelberg, 6130, pp.104-123, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13411-1〉. 〈inria-00463491v2〉

Partager

Métriques

Consultations de la notice

304

Téléchargements de fichiers

170