Skip to Main content Skip to Navigation
New interface
Conference papers

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 (1965 - 2019), 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.
Complete list of metadata

Cited literature [17 references]  Display  Hide  Download
Contributor : Angelos Mantzaflaris Connect in order to contact the contributor
Submitted on : Saturday, October 30, 2010 - 4:40:49 PM
Last modification on : Thursday, August 4, 2022 - 4:52:38 PM
Long-term archiving on: : Friday, December 2, 2016 - 9:03:06 AM


Files produced by the author(s)



Angelos Mantzaflaris, Bernard Mourrain. A Subdivision Approach to Planar Semi-algebraic Sets. 6th International Conference, GMP, Jun 2010, Castro Urdiales, Spain. pp.104-123, ⟨10.1007/978-3-642-13411-1_8⟩. ⟨inria-00463491v2⟩



Record views


Files downloads