Finding at least one point in each connected component of a real algebraic set defined by a single equation

Fabrice Rouillier; Marie-Françoise Roy; Mohab Safey El Din

inria-00099275, version 1

Finding at least one point in each connected component of a real algebraic set defined by a single equation

Fabrice Rouillier ()^a^, 1, Marie-Françoise Roy^b, Mohab Safey El Din^c^, 1

Journal of Complexity 16, 4 (2000) 716-750

Abstract: Deciding efficiently the emptiness of a real algebraic set defined by a single equation is a fundamental problem of computational real algebraic geometry. We propose an algorithm for this test. We find, when the algebraic set is non empty, at least one point on each semi-algebraically connected component. The problem is reduced to deciding the existence of real critical points of the distance function and computing them.

a – INRIA
b – UNIVERSITE DE RENNES I IRMAR
c – UNIVERSITE PARIS 6
1: SPACES (INRIA Lorraine - LORIA)
INRIA – CNRS : UMR7503 – Université Henri Poincaré - Nancy I – Université Nancy II – Institut National Polytechnique de Lorraine (INPL)

inria-00099275, version 1
http://hal.inria.fr/inria-00099275
oai:hal.inria.fr:inria-00099275
From: Publications Loria <>
Submitted on: Tuesday, 26 September 2006 08:52:19
Updated on: Thursday, 28 September 2006 15:22:46

See detailed view

Export

Bibtex EndNote TEI RefWorks

<?xml version="1.0" encoding="UTF-8"?>
<listBibl xmlns="http://www.tei-c.org/ns/1.0" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:mml="http://www.w3.org/1998/Math/MathML">
<listBibl type="article"><head>Articles in peer-reviewed journal</head>
<biblStruct type="article" xml:id="inria-00099275"><analytic>
<author><persName><forename>Fabrice</forename><surname>Rouillier</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">SPACES</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<author><persName><forename>Marie-Françoise</forename><surname>Roy</surname></persName></author>
<author><persName><forename>Mohab</forename><surname>Safey El Din</surname></persName>
<affiliation>
<orgName type="laboratory">INRIA Lorraine - LORIA</orgName>
<orgName type="team">SPACES</orgName>
<country>FR</country>
<orgName type="institution">INRIA</orgName>
<orgName type="institution">CNRS : UMR7503</orgName>
<orgName type="institution">Université Henri Poincaré - Nancy I</orgName>
<orgName type="institution">Université Nancy II</orgName>
<orgName type="institution">Institut National Polytechnique de Lorraine (INPL)</orgName>
</affiliation>
</author>
<title type="main" level="a">Finding at least one point in each connected component of a real algebraic set defined by a single equation</title></analytic><monogr><title level="j" type="main">Journal of Complexity</title><imprint><publisher>none</publisher><biblScope type="publicationDate">2000-00-00</biblScope><biblScope type="vol">16</biblScope><biblScope type="issue">4</biblScope><biblScope type="pp">716-750</biblScope></imprint></monogr><idno type="HALid">http://hal.inria.fr/inria-00099275</idno></biblStruct>
</listBibl>
</listBibl>