Topological Complexity of Motion Planning

   Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Topological Complexity of Motion Planning

Abstract. In this paper we study a notion of topological complexity TC (X) for the motion planning problem. TC (X) is a number which measures discontinuity of the process of motion planning in the configuration space X . More precisely, TC (X) is the minimal number k such that there are k different "motion planning rules," each defined on an open subset of X× X , so that each rule is continuous in the source and target configurations. We use methods of algebraic topology (the Lusternik—Schnirelman theory) to study the topological complexity TC (X) . We give an upper bound for TC (X) (in terms of the dimension of the configuration space X ) and also a lower bound (in terms of the structure of the cohomology algebra of X ). We explicitly compute the topological complexity of motion planning for a number of configuration spaces: spheres, two-dimensional surfaces, products of spheres. In particular, we completely calculate the topological complexity of the problem of motion planning for a robot arm in the absence of obstacles.     

Topological Complexity with Continuous Operations

The topological complexity of algorithms is studied in a general context in the first part and for zero-finding in the second part. In the first part thelevel of discontinuityof a functionfis introduced and it is proved that it is a lower bound for the total number of comparisons plus 1 in any algorithm computingfthat uses only continuous operations and comparisons. This lower bound is proved to be sharp if arbitrary continuous operations are allowed. Then there exists even a balanced optimal computation tree forf. In the second part we use these results in order to determine the topological complexity of zero-finding for continuous functionsfon the unit interval withf(0) ·f(1) < 0. It is proved that roughly log₂log₂?⁻¹comparisons are optimal during a computation in order to approximate a zero up to ?. This is true regardless of whether one allows arbitrary continuous operations or just function evaluations, the arithmetic operations {+, −, *, /}, and the absolute value. It is true also for the subclass of nondecreasing functions. But for the subclass of increasing functions the topological complexity drops to zero even for the smaller class of operations.     

Topological Complexity of the Relative Closure of a Semi-Pfaffian Couple

Gabrielov introduced the notion of relative closure of a Pfaffian couple as an alternative construction of the o-minimal structure generated by Khovanskii’s Pfaffian functions. In this paper, we use the notion of format (or complexity) of a Pfaffian couple to derive explicit upper bounds for the homology of its relative closure. We consider both the singular and the Borel–Moore homology theories.     

On the Complexity of Isolating Real Roots and Computing with Certainty the Topological Degree

In this contribution the isolation of real roots and the computation of the topological degree in two dimensions are considered and their complexity is analyzed. In particular, we apply Stenger's degree computational method by splitting properly the boundary of the given region to obtain a sequence of subintervals along the boundary that forms a sufficient refinement. To this end, we properly approximate the function using univariate polynomials. Then we isolate each one of the zeros of these polynomials on the boundary of the given region in various subintervals so that these subintervals form a sufficiently refined boundary.     

拓扑遍历与拓扑双重遍历

令X为紧致度量空间,f:X→X为连续映射,U,V为X的任意非空开集,若{n>0|fn(U)∩V≠ )为正上密度集,则称f拓扑遍历.f拓扑双重遍历意味着f×f拓扑遍历.本文在[2]的基础上进一步讨论拓扑遍历与拓扑双重遍历映射的性质.     

Topological designs

We give an exponential upper and a quadratic lower bound on the number of pairwise non-isotopic simple closed curves which can be placed on a closed surface of genus $g$ such that any two of the curves intersects at most once. Although the gap is large, both bounds are the best known for large genus. In genus one and two, we solve the problem exactly. Our methods generalize to variants in which the allowed number of pairwise intersections is odd, even, or bounded, and to surfaces with boundary components.     

Topological horseshoes

When does a continuous map have chaotic dynamics in a set ? More specifically, when does it factor over a shift on symbols? This paper is an attempt to clarify some of the issues when there is no hyperbolicity assumed. We find that the key is to define a ``crossing number' for that set . If that number is and 1$">, then contains a compact invariant set which factors over a shift on symbols.

     

Topological groups

The paper deals with the investigations in the theory of topological groups from 1965 to 1980. The fundamental sections are: group topologies, morphisms, commutativity and its generalizations, finiteness and discreteness conditions for subgroups of locally compact groups, manifolds. One gives the formulation of all the basic results and one indicates the unsolved problems.Translated from Itogi Nauki i Tekhniki, Seriya Algebra, Topologiya, Geometriya, Vol. 20, pp. 3–70, 1982.     

Embedding of Countable Topological Semigroups in Simple Countable Connected Topological Semigroups

We prove that any countable Hausdorff topological (inverse) semigroup is topologically isomorphically embedded into a simple countable connected Hausdorff topological (inverse) semigroup with identity.     

Complexity of diagrams

A diagram is an undirected graph corresponding to the covering relation of a finite poset. We prove that three decision problems related to diagrams are NP-complete.