Computing Minimum-Link Path

in a Homotopy Class

amidst Semi-Algebraic Obstacles in the Plane

D. Grigoriev^{1}^{♭}

Dept. of Computer Science, Penn State University, USA

and

Steklov Inst. for Mathematics, Acad. of Sci. of Russia, St-Petersburg, Russia

A. Slissenko^{2}^{♯}

Dept. of Informatics, Univ. Paris-12, France and Inst. for Informatics, Acad. of Sci. of Russia, St-Petersburg, Russia

Abstract. Given a set of semi-algebraic obstacles in the plane and two points in the same connected component of the complement, the problem is to construct a polygonal path between these points which has the minimum number of segments (links) and the minimum ‘total turn’, that is the sum of absolute values of angles of turns of the consecutive polygon links. We describe an algorithm that solves the problem spending polynomial time to construct one segment of the minimumlink and minimum-turn polygon if to use a modification of real RAMs which permits to handle the solutions of algebraic equations. It is known that the number of segments in such a minimum-link polygon can be exponential as function of the length of the input data or even of the degree of polynomials representing the semi-algebraic set. In fact, we describe how to construct a minimum-link-turn path for a given class of homotopy (whose shortest path has no self-intersections), and provide a rigorous and rather a universal way of reasoning about homotopy classes in contexts related to algorithms. It was previously shown by Heintz-Krick-Slissenko-Solernó that a shortest path in the situation under consideration is semi-algebraic, and an extended real RAM that is able to compute integrals of algebraic functions can find it in polytime.

1 Introduction.

We consider the problem of constructing minimum-link minimum-turn polygon amidst semi-algebraic obstacles in the plane either for a given homotopy class or globally. Usually this problem is motivated by robotics (see, e. g. [HS94, MPA92,

1 Address: Dept. of Comput. Sci., Penn State University, University Park, PA 16802, USA. E-mail: grigorie@sol4.cse.psu.edu ♭Supported by a grant of Ministère de l’Enseignement Supérieur et de la Recherche de la France (December 1995 – January 1996) and by NSF grant CCR-9424358.

2 Address: Dept. of Informatics, University Paris-12, 61 Av. du Gén. de Gaulle, 94010, Créteil, France. E-mail: slissenko@univ-paris12.fr ♯Partially supported by INTAS-93-2530-ext project.

MRW92]): if a robot is hard to turn then we try to minimize, firstly, the number of turns, and secondly, the total turn that is the sum of absolute values of all turns. We consider the case of semi-algebraic obstacles in the plane. It is known that one cannot reduce this case to the case of polygonal obstacles, approximating the initial ones, without exponential growth of the complexity of representation (e. g. see [HKSS94, HKSS93]).

1.1 Semi-algebraic obstacles. A semi-algebraic [BCR87] set S in the plane is a set represented by a disjunctive normal form formula which atoms are polynomial equations and inequalities:

⋁_{1≤i≤N_{1}} ⋀_{1≤j≤N_{2}} f_{i,j}ω_{i,j}0  (1)

where f_{i,j} ∈ Z[x, y] and ω_{i,j} ∈ {≤, <, =}. We treat the set as representing obstacles. It may consist of many connected components, and every its connected component will be also called an obstacle. Zero-dimensional componets, i. e. isolated points can hardly be obstacles, so we exclude them from the set. These points can be easily described by a formula of Tarsky algebra with small number of quantifiers and containing polynomials of small number of variables. As we consider the complexity on a qualitative level, namely, polynomial, exponential, we do not need to go into details of descriptions of the sets under consideration. Our starting set is (1), denote it by S, and the complexity of its representations is measured by the following parameters: d, the maximum of degrees of the polynomials f_{ij}, and M, the least integer such that 2^{M} bounds the absolute values of the coefficients of f_{ij}. Related sets as the closure S̄, the interior S^{∘}, the boundary S^{β}, the complement coS of S, the set of isolated points of S etc. can be represented by formulas of Tarski algebra which complexity (the number of quantifiers, the number of variables in polynomials involved) is bounded by a constant. We need a procedure which, given such a set, constructs its connected components and a procedure that recognizes whether two points are in the same connected component. Within the mentioned context such polytime procedures are known (for general case see, e. g. [HRS90, Gri88, GV92, Ren92], for 2-dimensional case see also [AM88]). To assure the existence of a shortest path, the space admissible for trajectories is constituted by open space coS̄, that is the free space, and by the boundary Δ=_{df} S^{β}. The trajectories can go anywhere in the free space, but they are forbidden to go through boundaries though allowed to border them alongside.

1.2 Path Problems. A path or curve is a continuous piecewise smooth image of a closed segment. A simple path or quasi-segment is a path without self-intersections. Let s and t be two points in the free space. We consider paths between s and t not intersecting obstacles. When speaking about the order of points on a path ψ between s and t we mean later or after in the sense of a continous, ‘length increasing’ parametrisation ψ = {ψ(t)}_{0≤t≤1} of ψ such that s = ψ(0), t = ψ(1).

A polygonal path is minimum-link if it has minimum possible number of links among all polygonal paths between s and t in the same class of homotopy of the free space, and such a path is globally minimum-link if its number of links is minimum among all polygonal paths between s and t . Such a minimum-link (for a class of homotopy or globally) polygon always exists, is not unique and may have exponential number of links (for lower bound see [HKSS94, HKSS93], and for upper bound see [HRS94]). The latter fact implies that it is reasonable to estimate the complexity of construction of a minimumlink path in terms of the complexity of building one link. Turn of two segments [X, Y] and [Y, Z] is the angle between vectors \overrightarrow{XY} and \overrightarrow{Y Z}. (The angle between these two vectors is the angle between the ray emanating from X in the direction \overrightarrow{XY} and the ray emanating from X in the direction parallel to \overrightarrow{Y Z}). Total turn of a polygonal line is the sum of absolute values of turns of all its consecutive links, say, from s to t . Minimum-link path is minimumturn if its total turn is minimum among all minimum-link paths. Our construction of a minimum-link path uses as an initial information a shortest path in the same class of homotopy of the free space; to get a globally minimumlink path we start from the graph of ‘shortest paths’ constructed in [HKSS94]. A shortest path is a path between s and t having the minimum length in its class of homotopy. For the case of semi-algebraic obstacles in the plane it was shown in [HKSS94] that a shortest path can be constructed in polytime by an extended version of real RAM [BSS89] that is able to calculate in polytime integrals of algebraic functions. For the purposes of this paper as a computational model we use another extension which we call a real RAM with equation solver. It allows at a step of computation to compute a root of a polynomial with coefficients computed at previous steps. In the usual real RAM [BSS89] the admitted polynomials have degree 1, so rational operations can be performed. Since a real RAM is a generalization of usual RAM (e. g. [Pap94]), polytime algorithms for bitwise models can be implemented on the model we consider. Slight development of the construction of [HKSS94] gives an algorithm (for a usual RAM) that outputs a path whose length is ε-close to the shortest paths length and which time complexity is polynomial in the complexity of representation of obstacles and in log \frac{1}{ε}. The problem of constructing a shortest path in R^{3} even amidst polyhedral obstacles is known to be NP-hard [CR87].

1.3 Previous results.

The problem of minimizing the number of links of a polygonal path amidst polygonal obstacles and the total turn was studied in the case when obstacles are polygonal, see e. g. [MRW92], [HS94], [CGM^{+}95], and section 4.4.2 in [MS95]. A more complicated problem of minimizing the length of minimum-link paths is considered in [MPA92]. In [HS94] the authors consider also the problem of constructing a minimum-link path for a given class of homotopy, again for polygonal obstacles. However, no article known to us does contain rigorous reasoning about classes of homotopy.

1.4 Our result. Our contribution to the minimum-link problem consists of, firstly, considering the problem for semi-algebraic obstacles and, secondly, in presenting rather a universal method of rigorous reasoning about paths in relation to classes of homotopy in algorithmic context. The method implies a subroutine for fast testing of homotopicity of two paths. We prove that for any class of homotopy containing a shortest path without selfintersections and represented by such a path one can construct a minimum-link, minimum-turn path spending polytime to construct a single link of the path. (The requirement of being not self-intersecting is not very restrictive.) And the same is valid for constructing a globally (thus regardless of a class of homotopy) minimum-link, minimum-turn path. In contrast with usual shortest path, where an ϵ-approximation to the length can be found by a usual RAM in time polynomial in the length of input and that of 1/ε (or even of log(1/ε) for 2-dimensional case), the problem of approximation of minimum-link paths is more delicate and is not considered here.

2 Shortest and Minimum-Link Paths of a Given Homotopy Class

The basic observation of [HKSS94] (though not stated explicitly) is that the shortest paths between two algebraic points s and t , of all classes of homotopy can be represented by a graph of polynomial size with edges weighted by the lengths of pieces of locally convex algebraic curves. The lengths of these pieces can be transcendental. But up to this point the graph can be found in polytime by a RAM (the weights can be computed on an extended real RAM which allows to compute integrals of algebraic functions). Every class of homotopy has exactly one shortest path. We will consider only shortest paths without self-intersections just to simplify the constructions.

2.1 Structure of minimum length paths. Let S be a semi-algebraic set. We assume (without loss of generality) that the two end points s and t of our paths are inside a square which boundaries are obstacles, and that the points lie in the free space, but for technical reasons are viewed as infinitely small obstacles. Denote by B(X, r) the open ball centered at X and of radius r, and by B̄(X, r) its closure. A path ψ intersects the boundary Δ at its point X ∈ Δ if for all small enough ε > 0 there is a closed quasi-segment σ ⊆ Δ ∩ B(X, ε) such that B(X, \frac{ε}{2}) \ σ consists of two connected components each containing points of ψ. It is clear that a shortest path in the free space is a rectilinear segment. If its end meets an obstacle the segment must be locally supporting at the point of contact with the obstacle. Topologically it means that no small enough extension of the segment beyond the point of contact intersects the boundary. One can also define this property in Tarski algebra. A segment σ = [σ^{−}, σ^{+}] is (locally) supporting to the boundary Δ at a point X ∈ Δ ∩ σ if for every small enough ε > 0 either to the left of or to the right of σ_{ε} = [X − ε(σ^{+} − σ^{−}), X + ε(σ^{+} − σ^{−})] there are no points of the obstacles in B(X, ε^{2}). ”To the left” and ”to the right” can be easiliy described in algebraic terms (e. g. in terms of the sign of an appropriate linear function).

A supporting segment [X, Y] is maximum to the right (to the left) if any its extension to the right (respectively, to the left) intersects obstacles. By an extension to the right we mean a segment of the form [X, Y + ε(Y − X)], an extension to the left is similar. A supporting segment is maximum if it is maximum in both directions.

A simple path is locally convex if the angle function of its tangent vector is monotone.

The (tangent) angle function of a smooth piece of the path is a function of, say, length parameter, giving for any point of this piece the (oriented) angle between the tangent vector at this point and some fixed direction.

For a junction point of two smooth pieces one can take as the value of the angle function the corresponding one-side limit of this function for any of these pieces.

A path is globally convex if it is a part of the boundary of its convex hull. Clearly, when a quasi-segment of a shortest path touches the obstacles and goes along the boundary, this piece of boundary must be locally convex, as well as the quasi-segment on the whole.

In the general case a shortest path is not globally convex, even its locally convex quasi-segment can be not convex because of a too big rotation (imagine a spiral corridor turning several times around some point). The path can change its convexity (i. e. the type of monotonicity of its angle function), but only via an inflection segment, i. e. a maximum rectilinear piece of the path such that small enough preceeding and subsequent pieces of the path are separated by the straight line determined by the segment.

The closure of pieces of the path between two consecutive inflection segments are monotone; we call a quasi-segment of a path monotone if for some its small extension (on the path) its angle func- tion is monotone.

It was shown in [HKSS94] that every shortest path φ consists of a polynomial number of semi-algebraic quasi-segments such that each of them is either an inflection segment of φ locally supporting to Δ at its both ends, or a semi-algebraic monotone quasi-segment which is constituted of pieces of Δ or of rectilinear segments between such pieces, the latter being locally supporting to the boundary at both its ends (imagine going around a circular saw blade as obstacle).

The first and the last segments of the shortest paths under consideration will be treated as inflection segments.

Let φ be a shortest path. Its standard alternating representation (or decomposition) is the following (finite) sequence D_{φ} of quasi-segments: the quasisegments D_{φ}(2k − 1), k ≥ 1, are the consecutive inflection segments of φ; each quasi-segment D_{φ}(2k), k ≥ 1, is the monotone quasi-segment of φ constituted by the right end of D_{φ}(2k − 1), left end of D_{φ}(2k + 1) and by the piece of φ between these ends (this piece may be empty).

2.2 Graph of shortest paths. We can represent the shortest paths of all homotopic classes as a graph G = G_{S}, as it was done in [HKSS94] or in a ‘dual’ form as follows. As vertices V of the graph we take s , t and all points that are endpoints of segments, that are locally supporting to the obstacles at these endpoints, and which interior lies in the free space. Denote S^{e}=_{df} Δ \ V. Two vertices X and Y of V are connected by an edge if they are two endpoints of a locally supporting segment mentioned above (and this segment is considered as the ‘realization’ of the edge) or if this is not the case, but X and Y consitute two endpoints of a locally convex connected component of S^{e}. Denote by E the set of just defined edges. As we do not use lengths, neither of the mentioned connected components nor of the segments, the graph can de found in polytime by a RAM.

2.3 Representation of Homotopy Classes. We speak about paths between s and t that are homotopic in the free space. Generators. The plane is supposed to be oriented. As generators of the fundamental group of coS we take cuts that are in a way dual to usual generators as circles [ST80]. (We do not know whether this type of generators was explicitly mentioned elsewhere although it appears to be quite convenient for algorithmical needs.) Choose in every connected component of the obstacles a point, and launch from it a curve homeomorphic to a ray (we will call these curves cuts) such that all the cuts are pairwise disjoint and go to infinity. Attribute to each cut a letter. The set of cuts constitutes a set of generators of a free group. Now one can define the homotopic type of a path in the plane as follows. Consider the consecutive intersections of the path with the cuts. We assume, without loss of generality, that the path intersects the cuts in isolated points. This sequence of intersections defines the following word: if the ith intersection is with a cut α in the clockwise direction then the ith letter of the word is α, otherwise α^{−1}. Reduce the word as an element of the corresponding free group to the incontractible (irreducible) one. Thus for every path ψ in the plane and for every set of generators F we have defined the word Ω_{F} (ψ) that can be considered as a representation of the class of homotopy of ψ (thereby, there is a bijective correspondence between the classes of homotopy and the elements of the free group). For technical reasons one can consider larger representations taking more points or launching more cuts from each point. The mentioned representation can then be obtained as a homomorphic image of such extended one.

3 Canonical Minimum-Link Polygon of a Homotopy Class.

Our construction of a minimum-link minimum-turn polygon for a given class of homotopy is described below. The construction is rather natural, the key problem is a rigorous proof of correctness of the construction; the situations that may appear are more diverse that one usually could imagine.

3.1 Canonical polygon.

Suppose that the shortest path φ of a homotopy class is given, and it has no self-intersections. We describe an algorithm that constructs a minimum-link minimum-turn polygon belonging to the same homotopy class as the path. This polygonal line will be called the canonical polygon of the homotopy class or of the shortest path φ. The canonical polygon will contain some extension of every inflection segment of the shortest path and will envelop in a minimum way each its monotone quasisegment up to the next inflection segment. The canonical polygon is defined by iterations of procedure NxtSeg, described below, until reaching the point t . The initial data are constituted by s , by the first segment of the shortest path which is an inflection segment, and by the subsequent monotone quai-segment that controls the process of extension of the first segment. The procedure NxtSeg constructs the next segment of the canonical polygon starting with its current argument which consists of a current segment σ = [σ^{−}, σ^{+}], and of a monotone quasi-segment D of φ ‘controlling’ the construction of the polygon such that σ^{+} lies on D ∩ Δ (and σ is supporting to the obstacles at σ^{+}). The procedure produces an extension σ̃ of the segment σ which is appended to the canonical polygon, a segment σ_{1} emanating from its last endpoint and supporting to the boundary, and a ‘controlling’ quasi-segment D_{φ}(k_{1}) that may stay unchanged.

3.2 Algorithm for constructing the canonical polygon.

The algorithm CanonPolyg for constructing the canonical polygon has as input two points s and t and the shortest path φ of some class of homotopy going from s to t . As its result the algorithm outputs the canonical polygon connecting the same two points and homotopic to φ. The algorithm starts with the first segment emanating from s (that is an inflection one) and tries to advance it as far as possible not leaving the class of homotopy. This is done by the algorithm NxtSeg. The iteration of the latter until the point t is reached, constitutes the algorithm CanonPolyg. Having finished one application of NxtSeg the algorithm CanonPolyg gets from NxtSeg a segment σ̃ that it appends to the canonical polygon, and a segment σ_{1} and a number k_{1} that it uses as input for NxtSeg at the subsequent iteration. Algorithm NxtSeg proceeds as follows, see Figure 1. Suppose that we have advanced up to some segment σ with the last point σ^{+} belonging to Δ and to a quasi-segment D = D_{φ}(k) which is not inflection one. Denote by R_{σ} the ray determined by vector \overrightarrow{σ^{−}σ^{+}} and starting at σ^{+}. Consider points X ∈ R_{σ}. Such a point may determine the longest segment [X, Y], where Y lies on D after σ^{+}, that is locally supporting to D ∩ Δ at Y and that does not intersect obstacles. It is unique due to the local convexity of D and absence of self-intersections of φ. Taking σ^{+} as initial value of X we move point X along the the ray R_{σ} towards ∞ until one of the following (not disjoint) events happens:

(a) The ray R_{σ} intersects at X the straight line determined by the subsequent inflection segment D_{φ}(k + 1).

(b) The segment [X, Y] meets an obstacle at a point Z ∈ [X, Y). The first event that happens determines X and Y. The interior of the triangle determined by the segments [σ^{+}, X], [X, Y] and the piece of D between σ^{+} and Y is free of obstacles. We extend σ from σ^{−} to X and append the latter segment to our polygon, and the take [X, Y] as the segment to play the role of σ for the next iteration. If it contains an inflection segment D_{φ}(k + 1) we set D = D_{φ}(k + 2). We write this algorithm in a more rigorous form, see Figure 1, to obtain its modification needed to construct globally minimum-link paths in the last section.

NxtSeg(input: σ, k; output: σ̃, σ_{1}, k_{1}): -- This procedure extends σ to σ̃ which will be appended to Q; -- constructs the next segment σ_{1} to be extended by the subsequent iteration; -- finds the next controlling monotone quasi-segment D_{φ}(k_{1}) that can be either D_{φ}(k) or D_{φ}(k + 2), -- the current controlling monotone quasi-segment being represented by D_{φ}(k). 1: Let D = D_{φ}(k); β = D_{φ}(k + 1).

Denote by R_{σ} the ray emanating from σ^{+} in the direction defined by vector \overrightarrow{σ^{−}σ^{+}}; and by R_{σ}^{+} its right ‘infinite’ end.

2: Construct the following three points X_{1}, X_{2}, X_{3} ∈ R_{σ}:

a:

If R_{σ} intersects the straight line determined by the inflection segment β, then X_{1} is the point of this intersection, otherwise X_{1} = R_{σ}^{+}.

b1:

X_{2} is the first point of intersection of R_{σ} with the obstacles. It always exists as the obstacles are inside a square.

b2:

In the graph of shortest paths look for segments ξ = [X′, Y′] such that ξ is supporting to D at Y′ ∈ D ∩ Δ, ξ is supporting to Δ at X′, ξ separates obstacles at X′ and Y′, the point X′ is at the same side of R_{σ} as Y′. Choose ξ for which the angle between \overrightarrow{X′Y′} and \overleftarrow{σ^{−}σ^{+}} is maximum. If there are several such segments take the longest one. Extend it towards R_{σ}, then X_{3} is the point of its intersection with R_{σ}.

3:

Take as X the point in {X_{1}, X_{2}, X_{3}} that is the closest to σ^{+}. Having found X take as Y the point on D to the right of σ^{+} such that Y ≠ σ^{+}, [X, Y] is the longest segment locally supporting to D at Y and not intersecting obstacls;

4: if [X, Y] contains β then k_{1} := k + 2 else k_{1} := k; 5: return (σ̃ := [σ^{−}, X]; σ_{1} := [X, Y]; k_{1})

Fig. 1. NxtSeg algorithm

4 Link and turn optimality of the canonical polygon.

Here we sketch proofs of the main properties of the canonical polygon.

Theorem 1 (Link and turn optimality of the canonical polygon.) The canonical polygon is minimum-link and minimum-turn.

This theorem is a direct consequence of Corollary 1 and Lemma 2 below.

4.1 Choice of Generators.

Assume that segments of any polygon P under consideration are numbered in the direction from s to t starting with 1. The kth segment of a polygon P will be denoted P (k), and the number of segments of P by #P. A segment P (k), 2 ≤ k ≤ #P − 1, is called monotone if the segments P (k − 1) and P (k + 1) are situated at the same side of the straight line determined by P (k), and is called inflection otherwise. Without loss of generality we assume that the boundary Δ everywhere bounds some non empty interior of the obstacles, maybe infinitely thin, thus a point of the boundary can be always moved ‘slightly’ inside obstacles. Let σ = [σ^{−}, σ^{+}] be a link of the canonical polygon Q of a shortest path φ. Its end σ^{+} is a blocking point if any extension of σ beyond this point in the direction \overrightarrow{σ^{−}σ^{+}} intersects the obstacles. A pair (α, β) of points of σ is a pair of its points of rigidity if α, β ∈ Δ, β lies on φ, and either α is a blocking point of the preceding segment σ′ of Q or the obstacles at α and β are separated by σ. The latter means that for some ε > 0 the (non empty) sets (B(α, ε) ∩ S) \ L_{σ} and (B(β, ε) ∩ S) \ L_{σ}, where L_{σ} is the straight line determined by σ, lie on opposite sides of L_{σ}. Points of rigidity of a segment will be used in constructions below as starting points of some cuts, and we wish that at this points the cuts do not intersect the segment. For this reason they will be always presumed to be ‘slightly’ perturbated, that is, a pair (α, β) will be replaced by a pair (α′, β′) of points situated inside the obstacles close enough to (α, β) (respectively) and to the boundary (to leave them on the appropriate side of σ, the perturbated point of a blocking point must be on the side opposite to the side of β). The meaning of ‘close enough’ will be clear from the context. To study the interaction of the canonical polygon Q with another polygon of the same class of homotopy we consider two consecutive segments σ_{0} and σ_{1} of Q and choose generators of the fundamental group as described below. Denote by ζ the articulation point of σ_{0} and σ_{1}, i. e. ζ = σ_{0}^{+} = σ_{1}^{−}, and by ζ̂ the convex (not greater π) angle determined by σ_{0} and σ_{1} that are considered as emanating from ζ. We distinguish 4 cases depending on the type of segments σ_{0} and σ_{1}, see Figure 2: (InfInf) σ_{0} and σ_{1} are both inflection segments; (InfMon) σ_{0} is an inflection segment and σ_{1} is a monotone one;

Fig. 2. Choice of generators.

(MonMon) σ_{0} and σ_{1} are both monotone segments; (MonInf) σ_{0} is an monotone segment and σ_{1} is an inflection one. To choose the points determining the tails of cuts we start from σ_{0}^{−} and go towards σ_{1}^{+}. Choose two points α and β of rigidity of σ_{0}, α being before β. If the previous segment has a blocking point, and σ_{0} is monotone then α is such a point. Choose two points γ and δ of rigidity of σ_{1}. Again if σ_{0} has a blocking point, and σ_{1} is monotone then γ is such a point. We suppose that if γ is a blocking point then it is on the side of σ_{0} opposite to β. ‘Slightly’ perturbate these points as it was described above, preserving the notations for them. For the pairs (α, β) and (γ, δ) we define 2 cuts in the following way, see Figure 2. Cut g_{α} immediately crosses σ_{0} and goes along σ_{0}, infinitely close to it, up to β, then goes to infinity inside ζ̂. Cut g_{β} goes along σ_{0}, infinitely close to it (between σ_{0} and g_{α}), in the direction to α, then crosses σ_{0} just before α, and after that goes to infinity outside ζ̂. If γ is outside ζ̂ then cut g_{γ} immediately crosses σ_{1}, and goes along σ_{1}, infinitely close to it, up to δ, and after that goes to infinity inside ζ̂. If γ is inside ζ̂ then cut g_{γ} immediately crosses σ_{1} and goes along σ_{1}, infinitely close to it, up to δ, and after δ goes to infinity outside ζ̂. If δ is outside ζ̂ then cut g_{δ} goes along σ_{1}, infinitely close to it (between σ_{1} and g_{γ}) , in the direction to γ, then crosses σ_{1} just before γ, and after that goes to infinity inside ζ̂. If δ is inside ζ̂ then cut g_{δ} goes along σ_{1}, infinitely close to it (between σ_{1} and g_{γ}) up to γ, crosses σ_{1} just before γ, and goes to infinity outside ζ̂. All the other cuts are chosen so that they do not touch the piece of Q between α and β, the mentioned points included. Without loss of generality consider that the cut g_{α} is crossed by σ_{0} counter clockwise (see Figure 2). Denote by V the word describing the homotopy type, i. e. the intersection with the chosen cuts, of prefix Q_{α} of Q from s to α, the latter point excluded. And by W denote the word of intersection with the cuts of the suffix of Q from δ to t , the former point excluded. Thus, the word describing the homotopy type of Q is of the form V UW, where U is constituted only by letters from

Σ=_{df} {g_{α}, g_{α}^{−1}, g_{β}, g_{β}^{−1}, g_{γ}, g_{γ}^{−1}, g_{δ}, g_{δ}^{−1}}.

Moreover, we consider that other cuts are chosen in such a way that the last letter V as well as the first letter of W are not from Σ. For example, for the case (InfInf) the homotopy type of Q in terms of the chosen generators is of the form V g_{α}^{−1}g_{β}g_{γ}g_{δ}^{−1}W.

4.2 Proof of Theorem 1. The link minimality of the canonical polygon follows from Lemma 1.

Lemma 1 For any polygon P and the canonical polygon Q of the same class of homotopy, for every k, 1 ≤ k ≤ #Q there exists m such that k ≤ m, and

(a) P (m) intersects Q(k) in a point X lying between any two rigidity points of Q(k),

(b) the prefix Q_{X} of Q starting at s and ending at X and the prefix P_{X} of P starting at s and ending at X have the same homotopic type,

(c) P (m) arrives at crossing with Q(k) from the side opposite to any point α that can constitute a pair (α, β) of points of rigidity of Q(k).

Proof. We proceed by induction on the number k of segments of Q. The case k = 1 is evident. Suppose the lemma is valid for the first k segments of Q. Consider the non trivial case when the kth segment is not the last one, then it has a consecutive one. Denote the kth and (k + 1)st segments of Q by σ_{0} and σ_{1} respectively. Choose the cuts to represent homotopies as described above. Let P (m_{0}) be the last segment of P which crosses Q at a point X lying between α and β and satisfies the induction hypothesis. It enters σ_{0} from the side opposite to α, and Q_{X} and P_{X} have homotopy type represented by the word V g_{α}^{−1}g_{β}. Within the choice of generators, the homotopy type of Q is of the form V g_{α}^{−1}g_{β}GW, where V, G and W are of the type described above. In particular, if σ_{1} is monotone then G = g_{γ}^{−1}g_{δ}, and if σ_{1} is inflection then G = g_{γ}g_{δ}^{−1}. Let G = g′g′′, where g′ and g′′ are defined as has been just described depending on the case under consideration. Now, to assure the demanded homotopy type the polygon P must realize g′ (that is to cross g_{γ} from the appropriate side) and then realize g′′. Suppose that such a crossing is done outside of [γ, δ]. Note that each pair of cuts, (g_{α}, g_{β}) and (g_{γ}, g_{δ}) determine a cut of the plane up to an infinitely narrow corridor between points α and β (and, respectively, γ and δ) with ‘walls’ constituted by the corresponding pieces of g_{α} and g_{β} (respectively, of g_{γ} and g_{δ}). And the segment P (m_{0}) has entered X in a ‘half’ plane determined by (g_{α}, g_{β}). To enter the other ‘half’ plane without crossing [α, β] it must go through the corridor from the side of β, but this is an obstacle, so this is impossible. Because of a similar reason it is impossible to penetrate in the corridor from the side of α. Now, the point X is in the intersection of two ‘half’ planes determined by (g_{α}, g_{β}) and (g_{γ}, g_{δ}). To respect the homotopy type the polygon P must realize an intersection with cuts that gives g′g′′. Suppose that σ_{1} is an inflection segment (the case when it is monotone is completely similar). Is it possible to have g_{γ}g_{δ}^{−1} without crossing [g_{γ}, g_{δ}]? Clearly not, because to do it the polygon P must penetrate the corridor between g_{γ} and g_{δ} that is impossible. Thus, P must cross (g_{γ}, g_{δ}) from the side opposite to γ, and the last such crossing must have the homotopy type V g_{α}^{−1}g_{β}G. Clear, this crossing can not be realized by P (m_{0}), but by a further segment of P. □ Corollary 1 Every canonical polygon is minimum-link.

Corollary 2 For any minimum-link polygon P and the canonical polygon Q of the same class of homotopy, for any k the kth segments of Q and P are either both monotone or inflection ones, and the kth segments of P and Q intersect each other. Corollary 1 is a straightforward consequence of Lemma 1, (a) and its condition on m. Corollary 2 is implied by Lemma 1 and minimality of P. The latter imposes an intersection of P (k) and Q(k).

Lemma 2 For any minimum-link polygon P and the canonical polygon Q of the same class of homotopy, and for any point X of intersection of an inflection segment of the canonical polygon Q with the corresponding (i.e. having the same number) inflection segment of P, the total turn of Q_{X} is not greater than the the total turn of P_{X}, where Q_{X} and P_{X} are the prefixes of respectively Q and P between s and X.

Proof. It is sufficient to compare turns between two consecutive inflection segments of the canonical polygon Q and that of the corresponding segment of another minimum-link polygon P, and to take into consideration Lemma 1, (c). Let σ_{0} and σ_{1} be two consecutive inflection segments of the canonical polygon Q. It is obvious, that the total turn of all monotone segments between σ_{0} and σ_{1} is equal to the total turn from σ_{0} to σ_{1} (it can be arbitrarily large). The basic observation is illustrated on the Figure 3: ξ_{0} and ξ_{1} are segments of P corresponding to Q (in the sense of Lemma 1). The angles to compare are φ (total turn modulo π from σ_{0} to σ_{1}), and ψ (total turn modulo π from ξ_{0} to ξ_{1}). Clearly, φ ≤ ψ, because the triangle XY Z is inside of the triangle XY V. □

Fig. 3. Comparing total turns.

5 Algorithm of Global Search and its Complexity.

Now we describe a wave algorithm which constructs a minimum-link path between s and t . It is based on the standard idea, as, for example, in Dijkstra’s shortest path algorithm. The algorithm starts from the graph of the shortest paths, denote it by G = (V, E). It advances simultaneously along all the paths constructing the corresponding canonical polygons link by link. The number of links gives the current value of weight, and the algorithm builds only polygons of the minimum weight. As landmarks of this search it takes inflection segments which direct the wave propagation and permit to determine a quasi-segment for applying slightly modified NxtSeg algorithm to calculate the link distance of the front of the current wave from s . To make this idea more precise denote by G_{infl} = (V_{infl}, E_{infl}) the following graph of inflection segments that will control the procedure. Let V_{infl} be the set of all pairs [xy] of vertices of G corresponding to inflection segments [x, y] (note that a segment cannot be a monotone segment for one path and be an inflection segment for another path). Two vertices [ux] and [yz] form an edge of E_{infl} iff the points x and y are connected by a path in G constituting a monotone quasi-segment. If two inflection segments are incident, i. e. have a common end point, then we consider them to be connected by an edge whose weight is 1. This quasi-segment connecting the vertices will be called the realisation of the edge, and will be denoted by D(Γ) for an edge Γ. One can remark that the canonical polygon is defined by consecutive inflection segments independently of its other parts as stated in Lemma 3.

Lemma 3 For any two adjacent vertices [uv] and [xy] of G_{infl} and whatever be simple paths φ and ψ of G containing as subpath the path from u via v via D([uv][xy]) via x to y, the pieces of their canonical polygons that lie between u and y are equal.

The piece of canonical polygon mentioned in Lemma 3 can be constructed by NxtSeg algorithm slightly modified in the following way. Denote the modified version NxtSegM. This algorithm is applied each time when the global algorithm finds an edge (α, β) of G_{infl} to analyse. NxtSegM starts from α being directed by the quasi-segment corresponding to (α, β), i. e. by D(α, β). It has as arguments a segment σ and the quasi-segment D = D(α, β) that is supposed to be not an inflection segment. The quasi-segment D can be empty if α and β are incident. The algorithm returns a segment playing the role of σ for the next iteration. One can recognize when it has finished the piece of canonical polygon between α and β; this happens when σ contains β. NxtSegM has an input σ, D, β and as output σ, where D = D(α, β) is a monotone quasi-segment directing the canonical polygon, and σ is a segment as in NxtSeg. The description of NxtSegM(input : σ, D, β; output : σ) can be obtained from the description of NxtSeg by expunging the initial comments in lines 3-5, the operators 1 and 4, and by deleting σ̃ and k in operator 5. To uniformize the description of the algorithm of global search append to G_{infl} two vertices [s s ] and [t t ] and connect them by zero-weight edges with all vertices corresponding to inflection segments of G emanating from s and t respectively. The algorithm MnLnkPath which construct a minimum-link polygon, and in fact all such polygons in a usual compressed form, proceeds as follows:

(a) All the edges of G_{infl} are classified as ”with calculated weight” and ”with not yet calculated weight”. Initially, the only edges with calculated weight equal to 0, are those that emanate from [s s ] and [t t ].

(b) The algorithm advances as in Dijkstra’s algorithm, starting from s but only via edges of G_{infl} with calculated weights. Having reached t it stops.

(c) The algorithm keeps a set of reached vertices with calculated weights which constitute the front of the wave. For each edge outgoing from such a vertice α it calculates its weight by constructing one segment of the canonical polygon, and hence augments its weight by one for all edges with not yet calculated weights. When canonical polygon reaches the corresponding inflection segment, the weight is calculated. If after this adding of 1 the set of edges with calculated weights has augmented, the algorithm make one step of the Dijkstra algorithm, maybe advancing from front vertices one edge farther to not explored vertices. And iterates this procedure. One can represent minimum-link paths by pointers which permit extract one such path in time polynomial in the number of its links.

Theorem 2 Algorithm MnLnkPath constructs a minimum-link path in time polynomial in the number of links of the path.

Theorem 3 A minimum-link path with minimum turn can be found in time polynomial in the number of links of the path.

Acknowledgements. The first author is thankful to the Department of Informatics of the University Paris-12 for the hospitability during his stay there for two months in 1995 and 1996.

References

[AM88] M. E. Alonso and Raimondo M. The computation of the topology of a planar semialgebraic set. Rend. Sem. Mat. Univers. Politecn. Torino, 46(3):327–342, 1988.

[BCR87] J. Bochnak, M. Coste, and M.-F. Roy. Géométrie algébrique réelle. Springer-Verlag, 1987.

[BSS89] L. Blum, M. Shub, and S. Smale. On a theory of computation and complexity over real numbers: NP-completeness, recursive functions and universal machines. Bull. Amer. Math. Soc., 1:1–46, 1989.

[CGM^{+}95] V. Chandru, S. K. Ghosh, A. Maheshwari, V. T. Rajan, and S. Saluja. NC-algorithms for minimum link path and related problems. J. of Algorithms, 19:173–203, 1995.

[CR87] J. Canny and J. Reif. New lower bound technique for robot motion planning problemms. In Proc. 28th Annu. IEEE Symp. on Foundations of Comput. Sci., pages 49–60, 1987.

[Gri88] D. Yu. Grigoriev. Complexity of deciding Tarski algebra. J. Symb. Comput., 5:65–108, 1988.

[GV92] D. Yu. Grigoriev and N. N. Vorobjov. Counting connected components of a semi-algebraic set in subexponential time. Computational Complexity, 2(2):133–184, 1992.

[HKSS93] J. Heintz, T. Krick, A. Slissenko, and P. Solernó. Une borne inférieure pour la construction de chemins polygonaux dans R^{n}. In Publications du département de mathématiques de l’Université de Limoges, pages 94–100. Université de Limoges, France, 1993.

[HKSS94] J. Heintz, T. Krick, A. Slissenko, and P. Solernó. Search for shortest path around semialgebraic obstacles in the plane. J. Math. Sciences, 70(4):1944– 1949, 1994. Translation into English of the paper published in Zapiski Nauchn. Semin. LOMI, vol. 192(1991), p. 163-173.

[HRS90] J. Heintz, M.-F. Roy, and P. Solernó. Sur la complexité du principe de Tarski-Seidenberg. Bull. Soc. Math. de France, 118:101–126, 1990.

[HRS94] J. Heintz, M.-F. Roy, and P. Solernó. Single exponential path finding in semi-algebraic sets. part 2: the general case. In Ch. L. Bajaj, editor, Algebraic Geometry and Its Applications, 1994.

[HS94] J. Hershberger and J. Snoeyink. Computing minimum length paths of a given homotopy class. Computational Geometry, 4:63–97, 1994.

[MPA92] J. S. B. Mitchell, C. Piatko, and E. M. Arkin. Computing a shortest k-link path in a polygon. In Proc. 33rd IEEE FOCS, pages 573–582, 1992.

[MRW92] J. S. B. Mitchell, G. Rote, and G. Woeginger. Minimum-link paths among obstacles in the plane. Algorithmica, 8:431–459, 1992.

[MS95] J. S. B. Mitchell and Suri S. A survey on computational geometry, volume 7 of Hanbooks in Operations Research and Management Sciences, chapter 7, pages 425–479. Elsevier Science B. V., 1995.

[Pap94] C. H. Papadimitriou. Computational complexity. Addison-Wesley, 1994.

[Ren92] J. Renegar. On the computational complexity and geometry of the firstorder theory of the reals. parts 1-3. J. Symb. Comput., 13(3):255–352, 1992.

[ST80] H. Seifert and W. Threlfall. A Textbook of Topology. Academic Press, 1980.

This article was processed using the L^{A}TEX macro package with LLNCS style