Volume 32, Number 3, 417-430, DOI: 10.1007/s00454-004-1107-5

Properness Defects of Projections and Computation of at Least One Point in Each Connected Component of a Real Algebraic Set

Mohab Safey El Din and Éric Schost

View Related Documents

Abstract

Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algebraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article we propose a new algorithm for the former 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 Pgr enables us to detect the connected components of a real algebraic set without critical points for Pgr. Our algorithm is based on this observation and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples.

Fulltext Preview

Image of the first page of the fulltext document