Computing roadmaps of semi-algebraic sets on a variety (1999)

We consider a semi-algebraic set <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> defined by <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s"> <mml:semantics> <mml:mi>s</mml:mi> <mml:annotation encoding="application/x-tex">s</mml:annotation> </mml:semantics> </mml:math> </inline-formula> polynomials in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k"> <mml:semantics> <mml:mi>k</mml:mi> <mml:annotation encoding="application/x-tex">k</mml:annotation> </mml:semantics> </mml:math> </inline-formula> variables which is contained in an algebraic variety <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper Z left-parenthesis upper Q right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>Z</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mi>Q</mml:mi> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">Z(Q)</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The variety is assumed to have real dimension <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k prime comma"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>k</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>,</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">k’,</mml:annotation> </mml:semantics> </mml:math> </inline-formula> the polynomial <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper Q"> <mml:semantics> <mml:mi>Q</mml:mi> <mml:annotation encoding="application/x-tex">Q</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and the polynomials defining <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> have degree at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="d"> <mml:semantics> <mml:mi>d</mml:mi> <mml:annotation encoding="application/x-tex">d</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We present an algorithm which constructs a <italic>roadmap</italic> on <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The complexity of this algorithm is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="s Superscript k prime plus 1 Baseline d Superscript upper O left-parenthesis k squared right-parenthesis"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>s</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>k</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">s^{k’+1}d^{O(k^2)}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We also present an algorithm which, given a point of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> defined by polynomials of degree at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="tau"> <mml:semantics> <mml:mi>τ</mml:mi> <mml:annotation encoding="application/x-tex">\tau</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, constructs a path joining this point to the roadmap. The complexity of this algorithm is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="k prime s tau Superscript upper O left-parenthesis 1 right-parenthesis Baseline d Superscript upper O left-parenthesis k squared right-parenthesis Baseline period"> <mml:semantics> <mml:mrow> <mml:msup> <mml:mi>k</mml:mi> <mml:mo>′</mml:mo> </mml:msup> <mml:mi>s</mml:mi> <mml:msup> <mml:mi>τ</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> <mml:msup> <mml:mi>d</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:msup> <mml:mi>k</mml:mi> <mml:mn>2</mml:mn> </mml:msup> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> </mml:msup> <mml:mo>.</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">k’ s \tau ^{O(1)} d^{O(k^2)}.</mml:annotation> </mml:semantics> </mml:math> </inline-formula> These algorithms easily yield an algorithm which, given two points of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> defined by polynomials of degree at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="tau"> <mml:semantics> <mml:mi>τ</mml:mi> <mml:annotation encoding="application/x-tex">\tau</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, decides whether or not these two points of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> lie in the same semi-algebraically connected component of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and if they do computes a semi-algebraic path in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper S"> <mml:semantics> <mml:mi>S</mml:mi> <mml:annotation encoding="application/x-tex">S</mml:annotation> </mml:semantics> </mml:math> </inline-formula> connecting the two points.