Properness defects of projections and computation of at least one point in each connected component of a real algebraic set

Mohab Safey El Din 1, 2 Eric Schost 3
2 SPACES - Solving problems through algebraic computation and efficient software
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algbraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article, we propose a new algorithm for this task, which avoids a hypothesis of properness required in many of the previous methods. We show how studying the set of non-properness of a linear projection enables to detect connected components of a real algebraic set without critical points. Our algorithm is based on this result and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples.
Type de document :
Article dans une revue
Journal of Discrete and Computational Geometry, Springer, 2004, 32 (3), pp.417-430. 〈10.1007/s00454-004-1107-5〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00099962
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 10:12:57
Dernière modification le : vendredi 13 avril 2018 - 01:32:12

Lien texte intégral

Identifiants

Collections

Citation

Mohab Safey El Din, Eric Schost. Properness defects of projections and computation of at least one point in each connected component of a real algebraic set. Journal of Discrete and Computational Geometry, Springer, 2004, 32 (3), pp.417-430. 〈10.1007/s00454-004-1107-5〉. 〈inria-00099962〉

Partager

Métriques

Consultations de la notice

147