Polytime Algorithm for the Shortest Path

in a Homotopy Class

amidst Semi-Algebraic Obstacles in the Plane

D. Grigoriev^{1}^{♭}

Department of Computer Science, Penn State University, USA and Steklov Institute for Mathematics, Academy of Sciences of Russia, St-Petersburg, Russia

A. Slissenko^{2}^{♯}

Department of Informatics, University Paris-12, France and Institute for Informatics, Academy of Sciences of Russia, St-Petersburg, Russia

Version of November 24, 1997

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 the shortest path between these points in a given class of homotopy. This path is unique and has some canonical form. We use the representation of homotopy classes in a way that is as general as the classical one. It consists in representing generators of a free group which describes the classes of homotopy by disjoint cuts [GS97] homeomorphic to rays. We show that given such a system of generators and a word representing a class of homotopy, one can contruct the shortest path of this class in time polynomial in the size of the word and in the size of the representation of the obstacles and the cuts. The class of homotopy may also be represented by a path, then the polynomial complexity will depend on the size of the representation of this path. As a technical notion we introduce one particular system of cuts, which we call an extremity basis, that proves to be especially convenient for algorithmic purposes.

1Address: Dept. of Comput. Sci., Penn State University, University Park, PA 16802, USA.

E-mail: grigorie@cse.psu.edu

♭Supported by NSF grant CCR-9424358.

2Address: 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.

1 Introduction.

We consider the problem of constructing the shortest path of a given class of homotopy between two points in a connected component of the complement of semi-algebraic obstacles. The problem of the shortest path is well known, e. g. see the surveys [SS90, MS95], and in particular has a motivation that arises from robot motion planning [Can88, Lat91]. It was considered mainly for the case of polygonal obstacles in the plane, for which case many algorithms have been developed. For the case of polyhedral obstacles in 3-dimensional Euclidean space it is NP-hard [CR87] in the general case, though admits polytime algorithms in some particular cases (see the surveys mentioned above). And in any case of polyhedral obstacles a path which length is ε-close to the length of the shortest path, can be found in time polynomial in \frac{1}{ε} and in the size of the representation of the obstacles that are presumed to be given by their vertices [Pap85, CSY94]. The case of semi-algebraic obstacles in the plane had been considered in [HKSS94] where it was shown 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. Slight development of the construction of [HKSS94] gives an algorithm (for a usual RAM [Pap94]) that outputs a path whose length is ε-close to the shortest path length and which time complexity is polynomial in the complexity of representation of obstacles and in log \frac{1}{ε}. Constructing the shortest path in a given class of homotopy was considered for polygonal obstacles in the plane in [HS94], but within a rather restricted setting. Namely, the space admissible for paths is a boundary-triangulated 2-manifold which is a simplicial complex in which all vertices are boundary vertices. Homotopy classes are represented by paths. This particular triangulation permits to construct straightforwardly a covering space and easily find the shortest path homotopic to the given one. The efforts of this paper are concentrated on other kind of problems related to unifying treatments of various metrics and improving particular data structures.

Our result. We show that for the case of semi-algebraic obstacles in the plane and for rather general way of representing classes of homotopy the problem of constructing the shortest path of a given class of homotopy is solvable in time polynomial in the size of all input data (i. e. in the size of representation of obstacles and of the class of homotopy) for bitwise models of computation, e. g. for a usual RAM, see theorem 1 at the end of the paper. A class of homotopy may be represented as an arbitrary piecewise semi-algebraic path or, and this is more interesting, as a word in a free group describing the homotopy classes with the same generality as the classical approaches [ST80]. As such a representation we consider a set of pairwise disjoint piecewise semi-algebraic cuts homeomorphic to rays and emanating from each component obstacle. This type of representation which is, in a way, dual to the classical one [ST80], was considered in [GS97]. As a technical notion we introduce one particular system of cuts, which we call an extremity basis, that proves to be especially convenient for algorithmic purposes.

1.1 Semi-Algebraic Obstacles In the Plane.

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 in a natural way, some precisions being done below. The set S may consist of many connected components that can be found inpolytime [Gri88, HRS90, GV92, Ren92]. Zero-dimensional componets, i. e. isolated points, can hardly be treated as obstacles, so we exclude them from the set in polytime. These points can be easily described by a formula of Tarski 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 versus non polynomial, we do not need to go into details of descriptions of the sets under consideration. Our starting set is S of the form (1), 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} is greater or equal to the absolute values of the coefficients of f_{ij}. Related sets such 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 number of quantifiers and number of variables are bounded by a constant, and which size is bounded by a polynomial in the size of the formula (1). 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 (see [GHSV90, GV92, HRS94], for 2-dimensional case see also [AM88]). To avoid trivialities and assure the existence of the shortest paths we make some polytime transformations of the initial set S. We suppose that the set is inside some square which complement is an obstacle. We eliminate isolated points of the set S. Furthermore, we wish to leave only one connected component for the trajectories. To do it we find the connected components of the complement of S and append to the obstacles all components of the complement except the one we are interested in and which is determined by the given end points of the paths under consideration. Thus, we have a set S without isolated points and which complement is 1-connected. Consider its boundary S^{β}. To make the treatment of obstacles technically simpler we slightly transform them. To describe the transformations and other notions, introduce some notations:

• B(X, r) is an open ball centered at X and of radius r, and \overline{B}(X, r) is its closure;

• ε-neighborhood of a set U is B(U, ε)=_{df} ∪_{X∈U} B(X, ε);

• σ^{−} and σ^{+} denote respectively the left and right end of an ordered simple path σ.

Now we wish to ”slightly inflate” 1-dimensional pieces of S^{β} to make them 2-dimensional with some interior. For this purpose we use extensions of reals by infinitesimals as in [GV88] where one can find necessary algorithmic technique. Remind that such an extension of a real close field K starts by introducing a formal variable, say ξ, with the property: 0 < ξ < α for all positive elements α from K. This element is called infinitesimal over K. It is, clearly transtendental over K. Then one constructs the real closure of the field K(ξ) that will be denoted by K̃(ξ). For an element α of K̃(ξ) its standard part belonging to K can be defined, see [GV88], and will be denoted by st_{K}(α), the field K̃(ξ) will be always clear from the context. In algorithmic constructions we actually deal with Q, Q̃, Q̃(ξ), ˜ Q̃(ξ) etc. A field K being fixed, we say that ξ′ is infinitesimal with respect to ξ, and write ξ′ << ξ, if ξ′ is infinitesimal for K̃(ξ). Summarize the notations related to infinitesimals:

• ξ > 0 will be an element infinitesimal relatively to R, and two more infinitesimals 0 < ξ_{2} << ξ_{1} << ξ will be needed.

• R_{0}=_{df} R̃(ξ), R_{1}=_{df} R̃_{0}(ξ_{1}) and R_{2}=_{df} R̃_{1}(ξ_{2}).

Now we consider the formulas defining obstacles, balls etc. over R_{0}. Below we will identify a set in R^{n} defined by a formula of Tarski algebra over Rwith the (semi-algebraic) set in R_{0}^{n} defined by the same formula over R_{0} if it does not lead to ambiguity.

To ”inflate” the 1-dimensional isolated pieces of the boundary, replace the obstacles, or only those points of them that do not contain points of S^{∘} in its small enough neighborhood, by their ξ-neighborhoods. This can be described in Tarski Algebra over the signature extended by ξ, and thus the appropriate algorithms must be used to find the conected components, see [GV88, Gri88, Ren92]. Finally, let Γ be the closure of the set of obstacles obtained after the transformations described above, and Δ be its boundary. The space coΓ will be called the free space and Γ̃=_{df} Δ ∪ coΓ will be the space admissible for trajectories we are going to consider. The trajectories can go anywhere in the free space, they are forbidden to go through boundaries though allowed to border them alongside. In the admissible space a shortest path between two points always exists and is semi-algebraic [HKSS94], and it is not unique in the general case (but it is unique in a given homotopy class, see below). We will denote the chosen ends of trajectories by s and t (from respectively ”source” and ”target”, a usual notation in robot motion planning), and for technical reasons will assume them to lie in the free space (otherwise replace them by infinitely close ones in the free space). To summarize the resulting properties of the situation note that Γ̃ (assumed to be non empty) consists of only one connected component and that all the connected components of the obstacles are closed semi-algebraic sets with non empty 1-connected interior (i. e. such that any loop in the interior is contractible [ST80]) and without non degenerated boundary that means, in particular, that from any point of the boundary one can make a small deplacement into the interior of the component. A connected component of the obstacles will be called a component obstacle or simply an obstacle.

1.2 Shortest Path Problem

A path or curve is a continuous piecewise smooth image of a closed segment. A simple path or a quasi-segment is a path without self-intersections. We consider only paths lying in Γ̃ and not intersecting Δ. 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 ψ. A path intersects the obstacles if it either intersects the boundary or contains interior points of the obstacles. A path in Γ̃ is admissible if it does not intersect the obstacles. By default we consider only admissible paths between two fixed points s and t in the free space, and when constructing an admissible paths by joining admissible quasi-segments by their end points we tacitly presume verifying the non intersecting obstacles by the path obtained by such a joining. When speaking about an 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) (if again to appeal to the motivation from robot motion planning ψ can be viewed as a trajectory of a robot with t playing the role of time). A shortest path between s and t in a class of homotopy is a path having the minimum length among all the paths in this class of homotopy.

The problem we consider is to find a shortest path in a given class of homotopy.

We consider below only semi-algebraic representations that reduce a curve to a sequence of simple quasi-segments. When speaking about occurrences of points we will not distinguish points and its occurrences in notations assuming that the necessary information is somewhere given. The following notations concerning paths between s and t will de used: for a path ψ and occurrences of points X, Y on this path • ψ_{X} denotes the prefix of ψ from s to the occurrence of X on this path;

• ψ_{XY} will denote the piece of ψ between specified occurrences of X and Y on this path, usually the occurrence of X will be before the occurence of Y. To estimate the complexity of our algorithms we consider only paths given by a piecewise simple semi-algebraic representation which will be for briefness called piecewise representation. As such a representation one may take a list (X, Φ_{1}, …, Φ_{m}) constituted of a starting point X and semialgebraic sets Φ_{i}, each such set being a simple curve with end points X_{i} and Y_{i} satisfying the obvious condition: one of the points {X_{1}, Y_{1}} is equal to X, the other coincides with one of the end point of Φ_{2}, the other end point of Φ_{2} coinsides with an end point of Φ_{3} and so on. One can assume also more efficient mode of piecewise representation of a curve. Namely, such a curve is represented as a list of systems of algebraic inequalities Ψ_{i}, each having the form

h_{0} = 0, h_{1} ≥ 0, …, h_{k} ≥ 0, where h_{j} ∈ Q(x, y, λ), λ ∈ [0, 1],

and such that for every λ ∈ [0, 1] the system has a unique solution in x, y. In this case λ plays the role of the time via the curve.

1.3 Locally Shortest Paths amidst Semi-Algebraic Obstacles in the Plane.

An admissible path φ between s and t is locally shortest if for all small enough ε > 0 it has minimum length among the paths connecting the same points and lying in B(φ, ε). Locally shortest path can be also described as locally non-contractible. It is intuitively clear that locally shortest paths have some canonical form [HKSS94]: in the free space it is a rectilinear segment and if its end meets an obstacle the segment must be locally supporting at the point of contact with the obstacle. Define this observation more precisely. Locally supporting topologically 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 rectilinear segment (or a straight line defined by a vector) σ = [σ^{−}, σ^{+}] is (locally) supporting to a set U at a point X ∈ U ∩ σ if for every small enough ε > 0 either to the left of or to the right of the intersection of the segment σ_{ε} = [X − ε(σ^{+} − σ^{−}), X + ε(σ^{+} − σ^{−})] with the ball B(X, ε^{2}) there are no points of U in this ball 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 path is locally supporting to a set U at a point X ∈ U if every its locally supporting line at X is locally supporting to U at this point. When speaking about local support without mentioning the set U we mean by default the set Γ̃ (or the boundary Δ which will be equivalent). 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 (the side is to be fixed to make the value definite) of this function for any of these pieces. A quasi-segment is locally convex if its angle function is monotone (not necessarily strictly monotone). A quasi-segment touching the boundary Δ will be called locally convex with respect to the boundary if it is locally convex and for any two of its close enough points belonging to Δ the convex hull of the quasi-segment between these points does not contain points of the free space. From now on by locally convex we mean it with respect to the boundary. We call a quasi-segment of a path monotone (on the path) if for some its small extension (on the path) its angle function is monotone. 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 or locally 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). Such a 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 locally convex (with respect to the boundary) and monotone on the path. A path is canonical if it is locally supporting to the obsctacles at all its points and its intersection with the free space consists of disjoint straight-line open segments, and its intersection with the obstacles consists of locally convex quasi-segments of the boundary Δ. Note that the property of being locally supporting to the obsctacles in the definition of canonical path is used only locally, namely, it is essential only for points of linking of the mentioned quasisegments, as each of them has this property in its non end points.

Proposition 1 ([HKSS94]) A path is locally shortest iff it is canonical.

As it was remarked in [HKSS94] 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 locally convex quasi-segment monotone on the path which, in its turn, 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 quasi-segments 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). The alternating representation of canonical path can be, obviously, found in polytime.

1.4 Graph of Locally Shortest Paths.

Locally convex quasi-segments sufficient to compose all shortest paths of all homotopic classes can be represented as a graph G, 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 rectilinear segments that are locally supporting to the obstacles at these endpoints, and which interior lies in the free space. Denote Δ^{e}=_{df} Δ \ V. Two vertices X and Y of V are connected by an edge if they are either two endpoints of a locally supporting segment mentioned above or consitute two endpoints of a locally convex connected component of Δ^{e}. The point corresponding to a vertex as well as the quasi-segment corresponding to an edge will be called its realization. We will not distinguish an element of the graph and its realization if the context permits to identify the meaning. Thus obtained graph has one shortcoming. Imagine that we have arrived at some vertex X of this graph following a locally shortest path with the last quasi-segment corresponding to an edge e_{ZX} from some vertex Z. Now we wish to extend the path in all possible admissible ways by one next quasi-segment represented in the graph. But not all such extensions are admissible because of a particular linking may loose local convexity. Sure, this property is verifiable in polytime. But one can make this verification just once and do not think about it later. Let k be the degree of a vertex X, and Z_{1}X, …, Z_{k}X be all edges incident to X. Make k copies of X, denote them X_{1}, …, X_{k}, and replace the edges Z_{1}X, …, Z_{k}X respectively by Z_{1}X_{1}, …, Z_{k}X_{k}, thus the edges incident to the former X have been disconnected, but the realizations of the edges have not changed. Now we connect by zero-edges, i. e. constituted by segments [X_{i}, X_{j}], only those vertices which give an admissible canonical linking. The resulting graph will be denoted by G = G_{_{Γ},s ,t} = (V, E) and will be called the graph of canonical quasi-segments or more briefly the canonical graph. As we do not use lengths of the involved edges the graph can de found in polytime by a usual RAM [HKSS94].

Lemma 1 The graph of canonical quasi-segments can be constructed in time polynomial in the size of representation of obstacles.

Obviously, every path between s and t in G is canonical and thus, locally shortest due to proposition 1. And inversely, every canonical path between s and t is represented in G. Thus we have

Lemma 2 A path between s and t is canonical (locally shortest) iff it is a path between vertices s and t in the graph of canonical paths.

2 Paths in Homotopy Classes

In this section we consider homotopy class representation used in our algorithmic treatment of homotopy classes.

2.1 Representation of Homotopy Classes.

We speak about paths between s and t that are homotopic in the free space. And to represent homotopy classes we use ray cuts of the plane [GS97] that is, in a way, dual to the classical representation [ST80] which is hard to treat algorithmically. (We do not know whether this type of representation was explicitly mentioned elsewhere although it appears to be quite convenient for algorithmic purposes.) Generators. The plane is supposed to be oriented. As generators of the fundamental group of coS we take semi-algebraic cuts of the plane by pairwise disjoint homeomorphic images of rays as described below. Such a ray will be also called a cut. If not to mention the complexity of representation of cuts we can assume that each cut has polynomial complexity with respect to the complexity of the obstacles. Choose in every component obstacle one or more points (using,say [GV88]), and launch from every point one cut such that all the cuts are pairwise disjoint and go to infinity. (In fact it suffices to demand that cuts are pairwise non intersecting, but such a generality is not really needed. Another possible generalizaation is to launch several rays from one point, though being treatable, seems to be useless.) Attribute to each cut an individual letter. The set F^{1} these letters constitutes a set of generators of a free group. The set of inverses of letters of F will be denoted by F^{−1}, and the their union by F =_{df} F^{1} ∪ F^{−1}. For w ∈ F we denote by cut(w) the cut corresponding to w, i. e. cut(α) = cut(α^{−1}) = α for α ∈ F^{(1)}, and by start(w) denote the point from where the cut(w) emanates. If we choose in every component obstacle exactly one point and launch from it exactly one cut then we speak about a minimal basis otherwise we speak about an arbitrary basis. 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. An intersection via a non degenerated quasi-segment is considered as one intersection (such ”pathological” intersection can be easily avoided by a small displacement of cuts, but we can treat the general situation), and the direction of each intersection in determined by the orientation of the plane. Another degenerated case is the case of a touch of a cut by the path without intersecting it; in this case there is no intersection though the touch may constitute a segment. This sequence of intersections defines the following word Ω̂_{F} (ψ): if the ith intersection is with a cut α and goes in the clockwise direction then the ith letter of the word is α, otherwise α^{−1}. Reduce the word as an element of the free group to the incontractible (irreducible) one and denote the resulting word Ω_{F} (ψ) that can be considered as a representation of the class of homotopy of ψ. If F is fixed and clear from the context we will omit the indice F in the just introduced mappings. The empty word over F will be denoted here by 1.

Lemma 3 For any basis F 2 paths φ_{0} and φ_{0} with the same ends are homotopic iff the irreducible words over F corresponding them are equal: Ω_{F} (φ_{0}) = Ω_{F} (φ_{1}). For every minimal basis F the mapping Ω_{F} is a bijection between homotopy classes and words over F.

Lemma 3 is obvious as the free group defined by a minimal basis is isomorphic to the the fundamental group of the plane with deleted obstacles, and groups over larger bases are homomorphic to the fundamental group (all cuts except one in every component obstacle are mapped into 1).

Lemma 4 For any piecewise semi-algebraic path given as a piecewise simple representation φ the word Ω̂_{F} (φ), and thus the word Ω_{F} (φ), can be found in time polynomial in the size of representation of obstacles and in the sizes of representation of the basis and that of the path. In particular, the edges of the canonical graph can be labeled by the corresponding words in polytime.

Proof. Let φ be represented by a list (X, Φ_{1}, …, Φ_{m}) of non degenerated simple semi-algebraic paths. In polytime one can determine the consecutive end points X_{1} = X, X_{2}, …, X_{m}, X_{m+1} of the simple paths Φ_{i}, i. e. the pair X_{i}, X_{i+1} constitutes the end points of Φ_{i}, 1 ≤ i ≤ m, passed in this order if to start from X and to go along φ. Indeed, for each Φ_{i} find the connected components of its intersection with cuts and the connected components of the difference of Φ_{i} and the set of all cuts. The order among {X_{i}}_{i} permits to determine the order of the found components on the path and thus to define the word over F. Some special attention is demanded by the points X_{i} if they are on the cuts. For the second type of representation of curves, with parameter λ (mentioned at the end of the subsection 1.2), it is even easier to construct Ω̂_{F} (φ) in polytime. □

2.2 Extremity Basis

One type of generators proves to be especially efficient to construct shortest paths. To define it we choose some particular coordinate system (x, y). Firstly note that there is a direction for y for which every straight lines parallel to the y-axis has at most one point of Δ where this line is supporting Δ. All such directions can be described in Tarski algebra, and clearly, this set is not empty, as the number of directions for which Δ contains a straight-line segment parallel to y-axis, does not exceed (M · d), and the number of other directions with straight lines having two points supporting to the boundary does not exceed the square of the number of maximal locally convex quasi-segments of the boundary (”maximal” means that the segment cannot be extended along the boundary resting locally convex to the boundary). The number of such maximal locally convex quasi-segments is also bounded by a polynomial (though finiteness suffices). Thus we can choose a coordinate system (x, y) in the plane in such a way that each straight line parallel to the y-axis contains at most one point of Δ where it is supporting to the boundary. Find all such points of the boundary, let they be α′_{1}, …, α′_{k}. Construct points α_{1}, …, α_{k} ∈ (R_{1}^{2} ∩ Γ^{∘} in the interior of the obstacles that are infinitely close to α′_{1}, …, α′_{k} and such that st_{R_{0}}(α_{i}) = α′_{i}, 1 ≤ i ≤ k. Take rectilinear cuts starting from α_{i} in the positive or northen direction of y-axis (to give a clear geometric arguing we abuse the geographic notions for cardinality ponits). Such a set of cuts will be called an extremity basis of the fundamental group. It is evident that

Lemma 5 An extremity basis can be found in time polynomial in the size of representation of obstacles.

The crucial property of extremity bases is the following one.

Proposition 2 The word W = Ω̂_{F} (φ) over an extremity basis F corresponding to a locally shortest (or canonical) path φ is irreducible.

Proof. Suppose that W is reducible. Take any occurrence of a pair of reducible letters, let it be αα^{−1}, hence the path enters the cut α from the West. Consider the part of φ determining this occurrence. Denote by [X′, X] the segment of clockwise entering/leaving the cut α (i. e. φ comes into the cut α at X′ goes along up to X and goes out of the cut at X, normally, X = X′) and by [Y, Y′] the segment of anti-clockwise entering/leaving the cut α. Now we are interested in the part φ_{XY} of φ between these occurrences X and Y. Take any point Z among the most eastern points of φ_{XY}. This point is on the boundary, otherwise φ_{XY} could be shortened. Moreover, φ_{XY} is locally supporting to the boundary at this point because φ is canonical. Hence, Z is locally supporting for some vertical staright line. This point can be described by a system of algebraic equations with coefficients over R_{0} with finite number of solutions, and consequently, Z is defined over R_{0}. Thus, it is unique due to our choice of coordinates. That means that Z = st_{R_{0}}(β) for some β ∈ F. But the cut β which goes to the north must intersect φ_{XY}, and hence append some letter before the mentioned occurrence of α^{−1}. A contradiction. □

2.3 Constructing a Path in a Homotopy Class Given by a Word in the Fundamental Group

If we are given an arbitrary set of cuts it is not so simple to construct in polytime the shortest path in a given class of homotopy represented as a word over this set. Extremity basis is much simpler to treat (see below section 3). But how to transform efficiently a representation over one basis into the representation over another basis? A natural way is to construct any path in the corresponding class of homotopy. We show here how to do it in polytime.

Lemma 6 Let a homotopy class be given by a word over an arbitrary basis of cuts, each being piecewisely represented semi-algebraic curve. A path in this homotopy class be found in time polynomial in the size of representation of obstacles, in the size of the word and in the size of representation of the basis.

Proof. Let F be the alphabet of generators determined by an arbitrary system of cuts. Let W = w_{1} … w_{n}, w_{i} ∈ F, be an irreducible word over F determining a class of homotopy. We construct a path φ with Ω(φ) = W by the procedure described below. Roughly speaking, we contract the obstacle components to points, build a path corresponding to W and then inflate the obstacles back homotopically transforming the just built path. To realize this idea in polytime, the procedure firstly builds a new, auxiliary system of obstacles representing this contraction, constructs a path in the homotopy class W by a known polytime procedure, and then seeks an appropriate homotopy to come back to the initial obstacles. We take two more infinitesimals ξ_{2} << ξ_{1} << ξ and consider the plane over the field R_{2}. The infinitesimal ξ_{1} will be used to ”move” the starting ends of cuts into the interior of the obstacles, and ξ_{2} will be used to build an auxiliary system of obstacles. For each cut α′ such that start(α′) is on the boundary Δ, choose a point X in Γ^{∘} at a distance ξ_{1} from Δ and append to α the segment [X, α′]. It is possible as ξ_{1} << ξ. After that replace every cut α by the band B(α) of width ξ_{2} centered at α. More precisely, the band B(α) is a union of all segments s of length ξ_{2} with centers on α and having the property: if the center X of s is start(α) then s is orthogonal to α, otherwise it is orthogonal to a straight line locally supporting to α at X (the latter line is not unique in a finite number of points). Denote by σ̂_{α} the segment centered at start(α) that is the ”bottom” of B(α), it is orthogonal to α at start(α). Take the segment σ_{α} of length 2 · ξ_{2} parallel to σ̂_{α} and crossing B(α) at distance ξ_{2} from start(α). The segment σ_{α} lies in Γ^{∘}. Denote by B̂(α) the band B(α) together with σ_{α}, and by B̂ the union of B̂(α) over all cuts α. The set B̂ is the mentioned auxiliary system of obstacles. Denote by ζ_{i} the segment σ_{cut(w_{i})} if w_{i} = cut(w_{i}), and the inversed segment [σ_{cut(w_{i})}^{+}, σ_{cut(w_{i})}^{−}] if w_{i} = cut(w_{i})^{−1}. Construct the path Π = Π(W) in the following way. Build a path from s to ζ_{1}^{−} amidst the obstacles B̃, append to this path the segment ζ_{1}, build a path from ζ_{1}^{+} to ζ_{2}^{−} amidst B̃, append to it the segment ζ_{2}, and so on up to t . Such a path Π can be constructed in polytime using appropriate graphs of canonical quasi-segments. Now consider the original obstacles Γ̃ and original cuts. Going from s to t transform the path Π, which in the general case intersects the obstacles, into a semi-algebraic path φ which does not intersect them and such that Ω(φ) = W. One can imagine that we inflate the auxiliary obstacles back to the original obstacles and modify Π making it to go along the boundary of component obstacles in a proper direction. We will use notations for pieces of curves introduced in subsection 1.2. Speaking about points here we mean occurrences of points that can be indicated by a reference to the list defining the piecewisely represented semi-algebraic curve under consideration. Suppose that φ_{Z} is constructed up to some occurrence of Z ∈ Π, Ω(φ_{Z}) = Ω(Π_{Z}) = w_{1} … w_{k−1}, k ≥ 1. If k − 1 < n then w_{k} is defined, and we denote by S the component obstacle containing start(w_{k}). Having left Z but before reaching S, or t in the case when Ω(φ_{Z}) = W, the path Π may cross some component obstacles without intersecting any cut. Let S_{1} be the first such an obstacle, see Figure 1. Denote by X_{1} the first point of its intersection with S_{1}. Then look for the consecutive points of Π of its entering and leaving S_{1} without intersecting other component obstacles. Denote by Y_{1} the last point of leaving S_{1} among these points. Note that the piece Π_{X_{1}Y_{1}} does not intersect any cut. The two points X_{1} and Y_{1} divise the boundary of S_{1} into two quasi-segments. At least one of them, denote it by q has Ω(q) = 1 otherwise W does not define any class of homotopy because cut(w_{k}) (or the point t ) will lie in the domain between two other cuts emanating from S_{1}, and the entrance in this domain will be blocked by S_{1}. Note that q may intersect also cuts emanating from sources not in S_{1}. But no such a cut intersects Π_{X_{1}Y_{1}} and having once entered S_{1} such a cut must leave it and all these cuts intersecting S_{1} are

Figure 1: Going around obstacles.

pairwise disjoint. Replace the piece of Π between X_{1} and Y_{1} by q. That will give φ_{Y_{1}}. Clearly, Ω(Π_{ZY_{1}}) = 1 = Ω(φ_{ZY_{1}}). Now consider the case of S, i. e. the case when the first component obstacle intersected by Π after Z is S. Denote by X the first point of intersection of Π_{Zt} with S and by Y the last such point which precedes points of intersection of this path with other component obstacles. Again consider two quasi-segments of the boundary S^{β} determined by X and Y. One and only one of this quasi-segments has the property: when going from X along this quasi-segment the path Π meets the first intersection of cut(w_{k}) with the boundary S^{β} in correspondence with w_{k} (that is in the direction of ζ_{k}). Denote this quasi-segment by q. Now extend φ_{Z} by the segment Π_{ZX} and then by q. This gives φ_{Y}. One can show that Ω(φ_{Y}) = Ω(Π_{Y}) = w_{1} … w_{k}. Indeed, the first intersection of Π_{Y} with cut(w_{k}) is in the direction w_{k}. Other cuts may intervene between intersection with cut(w_{k}) only as words equal to 1, otherwise the initial W would not define any class of homotopy. To estimate the complexity notice that the number of perfomed modifications of the path does not exceed the number of points of intersection of the path with the obstacles that can be bounded by a polynomial (e. g. see [GV88]). □

3 Algorithm for the Shortest Path in a Given Homotopy Class.

Before describing an algorithm for constructing the shortest path of a given homotopy class we show that such a path is unique. Moreover, even locally shortest path is unique, and due to proposition 1 the canonical path is unique.

3.1 Uniqueness of Locally Shortest (Canonical) Path.

Proposition 3 There is a unique locally shortest (or canonical) path in a homotopy class. Thus, the unique shortest path of a homotopy class is the unique canonical path in this class.

Proof. Suppose that there are two different homotopic locally shortest paths φ_{0} and φ_{1} between s and t . The both are canonical (Lemma 1) and hence, piecewise semi-algebraic. Let Z be the last point of their longest common prefix φ_{Z}=_{df} (φ_{i})_{Z}. Denote by R the ray emanating from Z along the one-sided tangent to φ_{Z} at Z in the direction from s to t , see Figure 2. In a

Figure 2: Uniqueness of locally shortest (canonical) path.

neighborhood of Z the curves φ_{0} and φ_{1} lie on the same side of R, the ray itself not excluded. This observation is implied by the canonicity of the both curves. Indeed, the fact that one of the paths deviates from R means that there is an obctacle at Z, denote it by S. Suppose without loss of generality that S is to the right of φ_{Z} and, hence to the right of R. Then no canonical extension of φ_{Z} may go above R because that would mean a presence of an obstacle also to the left of R at Z. But then φ_{Z} intersects obstacles at Z. Thus, the both curves φ_{0} and φ_{1} lie on the same side of R. Let φ_{0} be the first curve that we meet (locally at Z) going in the clockwise direction from R around Z, and φ_{1} be the second one. Then φ_{0} must be a rectilinear segment in the free space in some neighborhood of Z, otherwise the both curves have at Z to the right of them some obstacle, and thus φ_{1} intersects the obstacles. Denote such maximal rectilinear segment of φ_{0} by [Z, Z_{0}]. Take (x, y)-coordinates centered at Z which x-axis goes along [Z, Z_{0}]. Take two infinitesimals ξ_{2} << ξ_{1} << ξ and consider the corresponding real closed extensions of R_{0}. Choose a cut α_{1} centered at some point infinitely close to Z with y-coordinate equal to −ε_{1} and launch from it the ray parallel to x-axis in the positive direction of this axis, see Figure 2. Add α_{1} to the alphabet of cuts. If Z_{0} ≠ t then φ_{0} goes from Z_{0} either below x-axis or above it. Add to the cuts a cut α_{2} infinitely close to Z_{0} with y-coordinate equal to −ε_{2} in the first case, and to +ε_{2} in the second case. If Z_{0} = t add nothing. In any case Ω(φ_{Z})α_{1} will be a prefix of Ω(φ_{1}), where Ω is considered over the extended alphabet. In the case Z_{0} = t the word Ω(φ_{0}) contain neither α_{1} nor α_{1}^{−1}, and, hence, differs from Ω(φ_{1}). In the case when φ_{0} goes from Z_{0} below x-axis the letter α_{2} appears in Ω(φ_{0}) just before α_{1}, and thus, Ω(φ_{0}) ≠ Ω(φ_{1}). Similar in the case when φ_{0} goes from Z_{0} above x-axis. A contradiction. □

3.2 Algorithm for Canonical Path.

Thus, in order to find the shortest path of a given class of homotopy it suffices to find the canonical path of this class. We describe an algorithm that constructs such a path when the class of homotopy is represented as the word in an extremity basis. This supposition does not diminish the generality. Indeed, if the class is represented by a piecewise semi-algebraic path, we can compute its representation over an extremity basis in polytime (Lemma 4), and an extremity basis itself can be found in polytime (Lemma 5). If the class is represented as a word over an arbitrary basis of cuts then one can found in polytime a piecewise semi-algebraic path in this class (Lemma 6) and again reduce the problem to the case when the class is given as a word over an extremity basis. The idea of the algorithm ShPthHomCl, see Figure 3, that transforms a word over an extremity basis into the canonical path corresponding to it, is to gradually build all paths corresponding to prefixes of the word advancing via the graph of canonical paths. The uniqueness of the canonical path and the irreducibility of words (see proposition 2) appearing while advancing assures that the number of paths under treatment will not go beyond the product of the number of vertices of the graph of canonical paths and the length of the word. Indeed, if two different canonical paths meet at the same vertex their words must be different otherwise the uniqueness would be violated (see proposition 3). In the description of the algorithm the following notations for paths p and q are used:

• p^{−} and p^{+} are respectively the first and the last vertex (and the corresponding points) of the path p;

• conc(p, q) is the concatenation of the paths p and q if p^{+} = q^{−};

• LastQSeg(q) is the last edge and the corresponding quasi-segment of the path q.

Lemma 7 Given an extremity basis, for every irreducible word H over this basis the algorithm ShPthHomCl verifies whether H defines a class of homotopy and if so, finds the shortest path in this homotopy class, in time polynomial in the size of representation of obstacles and in the length of H.

Proof. If H defines some class of homotopy then the shortest path with Ω(φ) = H exists and is unique due to proposition 3. And it is canonical (proposition 1). All the canonical paths are represented in G, and inversely, every path in G is canonical (Lemma 2). Thus, H defines some homotopy class iff there is a path φ in G between s and t with Ω(φ) = H. Hence, the algorithm is correct as it looks for all paths in G starting at s and corresponding to prefixes of H (it suffices to consider just prefixes of H due to proposition 2). So it rests to estimate the complexity of the algorithm. The algorithm analyzes all canonical paths emanating from s and corresponding to prefixes of H. If 2 such paths come to a same vertex their words must be different due to proposition 3 and lemma 3. Hence the number of paths neither in the set P aths nor in the set Ext_{p} does not exceed the product of the number of the vertices of G and the length of H. And the same bound is valid for the number of possibles sets Ext_{p} as p originates from P aths. At any step of the algorithm the length of a current prefix either augments or does not change (if the added edge of G represents the empty word, see proposition 2). The latter happens consecutively at most |E| times, since otherwise we get a loop in the canonical path which provides the empty word, hence it is contractible (cf. Lemma 3), and we can delete the loop, that condradicts proposition 3. Therefore the number of steps of the algorithm does not exceed |H| · |E|. □

We summarize the proved above in the following main result of the paper.

Theorem 1 The problem of constructing the shortest path in a given class of homotopy represented either as a word over a piecewise semi-algebraic basis of cuts or as a piecewise semialgebraic path is solvable in time polynomial in the size of representation of obstacles and in the size of representation of the class of homotopy.

Acknowledgements. The second auther is thankful to the Departments of Computer Science and of Mathematics of Pennsylvania State University for the hospitability during his stay there in February 1997.

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.

[Can88] J. F. Canny. The Complexity of Robot Motion Planning. ACM Doctoral Dissertation Awards. The MIT Press, 1988.

[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.

[CSY94] J. Choi, J. Sellen, and C.-K. Yap. Approximate Euclidean shortest path in 3-space. In Proc. 10th ACM Symp. on Computational Geometry, pages 41–48, 1994.

[GHSV90] D. Yu. Grigoriev, J. Heintz, Solernó, and N. N. Vorobjov, Jr. Comptage des composantes connexes d’un ensemble semi-algébrique en temps simplement exponentiel. C. R. Acad. Sci. Paris, 311, Ser. 1:879–882, 1990.

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

[GS97] D. Grigoriev and A. Slissenko. Computing minimum-link path in a homotopy class amidst semi-algebraic obstacles in the plane. In T. Mora and H. Mattson, editors, Proc. of the 12th Intern. Symp., AAECC’12, pages 114–129. Springer Verlag, 1997. Lect. Notes in Comput. Sci, vol. 1255.

[GV88] D. Yu. Grigoriev and N. N. Vorobjov. Solving systems of polynomial inequalities in subexponential time. J. Symb. Comput., 5:37–64, 1988.

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

[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ó. Description of the connected components of a semi-algebraic set in single exponential time. Discrete and Computational Geometry, 11:121–140, 1994.

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

[Lat91] J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, 1991.

[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.

[Pap85] C. H. Papadimitriou. An algorithm for shortest-path motion in three dimensions. Inform. Process. Lett., 20:259–263, 1985.

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

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

[SS90] J. T. Schwartz and M. Sharir. Algorithmic motion planning in robotics. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science. Vol. A, pages 391–430. Elsevier Science Publishers, B. V., 1990.

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

ShPthHomCl(F, H):

comment H is an irreducible word over an extremity basis F. The algorithm uses the graph G = (V, E) of canonical quasi-segments. The end points s and t of paths are fixed. end comment; Initialisation: forall σ ∈ E compute Ω_{F} (σ); P aths = {s }; comment P aths is a set of canonical paths under construction that will finally contain the resulting shortest path if it exists. end comment;

1: while_{0} P aths is non empty and does not contain a path between s and t do

WordExtension: 2: forall_{0} p ∈ P aths do 3: Ext_{p} := {p}; 4: P aths := P aths \ {p}; 5: while_{1} Ext_{p} ≠ ∅ do 6: forall_{1} q ∈ Ext_{p} do 7: Ext_{p} := Ext_{p} \ {q}; 8: forall_{2} quasi-segment σ ≠ LastSeg(q) of G incident to q^{+} do

9:  if_{0} q′=_{df} conc(q, σ) is canonical and Ω̂(q′) is a prefix of H

10: then if_{1} Ω(p) = Ω(q′) then Ext_{p} := Ext_{p} ∪ {q′} else P aths := P aths ∪ {q′} end if_{1}

end if_{0}
end forall_{2}
end forall_{1}
end while_{1}
end forall_{0}

end while_{0}; 11: if P aths = ∅ then return ”no path for H”

else return any path between s and t from the set P aths end if

Figure 3: Algorithm: Shortest Path in a Class of Homotopy.