TY - JOUR AB - A central problem of algebraic topology is to understand the homotopy groups πœ‹π‘‘(𝑋) of a topological space X. For the computational version of the problem, it is well known that there is no algorithm to decide whether the fundamental group πœ‹1(𝑋) of a given finite simplicial complex X is trivial. On the other hand, there are several algorithms that, given a finite simplicial complex X that is simply connected (i.e., with πœ‹1(𝑋) trivial), compute the higher homotopy group πœ‹π‘‘(𝑋) for any given 𝑑β‰₯2 . However, these algorithms come with a caveat: They compute the isomorphism type of πœ‹π‘‘(𝑋) , 𝑑β‰₯2 as an abstract finitely generated abelian group given by generators and relations, but they work with very implicit representations of the elements of πœ‹π‘‘(𝑋) . Converting elements of this abstract group into explicit geometric maps from the d-dimensional sphere 𝑆𝑑 to X has been one of the main unsolved problems in the emerging field of computational homotopy theory. Here we present an algorithm that, given a simply connected space X, computes πœ‹π‘‘(𝑋) and represents its elements as simplicial maps from a suitable triangulation of the d-sphere 𝑆𝑑 to X. For fixed d, the algorithm runs in time exponential in size(𝑋) , the number of simplices of X. Moreover, we prove that this is optimal: For every fixed 𝑑β‰₯2 , we construct a family of simply connected spaces X such that for any simplicial map representing a generator of πœ‹π‘‘(𝑋) , the size of the triangulation of 𝑆𝑑 on which the map is defined, is exponential in size(𝑋) . AU - FilakovskΓ½, Marek AU - Franek, Peter AU - Wagner, Uli AU - Zhechev, Stephan Y ID - 6774 IS - 3-4 JF - Journal of Applied and Computational Topology SN - 2367-1726 TI - Computing simplicial representatives of homotopy group elements VL - 2 ER - TY - JOUR AB - In this paper we present a reliable method to verify the existence of loops along the uncertain trajectory of a robot, based on proprioceptive measurements only, within a bounded-error context. The loop closure detection is one of the key points in simultaneous localization and mapping (SLAM) methods, especially in homogeneous environments with difficult scenes recognitions. The proposed approach is generic and could be coupled with conventional SLAM algorithms to reliably reduce their computing burden, thus improving the localization and mapping processes in the most challenging environments such as unexplored underwater extents. To prove that a robot performed a loop whatever the uncertainties in its evolution, we employ the notion of topological degree that originates in the field of differential topology. We show that a verification tool based on the topological degree is an optimal method for proving robot loops. This is demonstrated both on datasets from real missions involving autonomous underwater vehicles and by a mathematical discussion. AU - Rohou, Simon AU - Franek, Peter AU - Aubry, ClΓ©ment AU - Jaulin, Luc ID - 5960 IS - 12 JF - The International Journal of Robotics Research SN - 0278-3649 TI - Proving the existence of loops in robot trajectories VL - 37 ER - TY - JOUR AB - We study robust properties of zero sets of continuous maps f: X β†’ ℝn. Formally, we analyze the family Z< r(f) := (g-1(0): ||g - f|| < r) of all zero sets of all continuous maps g closer to f than r in the max-norm. All of these sets are outside A := (x: |f(x)| β‰₯ r) and we claim that Z< r(f) is fully determined by A and an element of a certain cohomotopy group which (by a recent result) is computable whenever the dimension of X is at most 2n - 3. By considering all r > 0 simultaneously, the pointed cohomotopy groups form a persistence module-a structure leading to persistence diagrams as in the case of persistent homology or well groups. Eventually, we get a descriptor of persistent robust properties of zero sets that has better descriptive power (Theorem A) and better computability status (Theorem B) than the established well diagrams. Moreover, if we endow every point of each zero set with gradients of the perturbation, the robust description of the zero sets by elements of cohomotopy groups is in some sense the best possible (Theorem C). AU - Franek, Peter AU - KrcΓ‘l, Marek ID - 568 IS - 2 JF - Homology, Homotopy and Applications SN - 15320073 TI - Persistence of zero sets VL - 19 ER - TY - JOUR AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map (Formula presented.) on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within (Formula presented.) distance r from f for a given (Formula presented.). The main drawback of the approach is that the computability of well groups was shown only when (Formula presented.) or (Formula presented.). Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of (Formula presented.) by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and (Formula presented.), our approximation of the (Formula presented.)th well group is exact. For the second part, we find examples of maps (Formula presented.) with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. AU - Franek, Peter AU - KrcΓ‘l, Marek ID - 1408 IS - 1 JF - Discrete & Computational Geometry TI - On computability and triviality of well groups VL - 56 ER - TY - CONF AB - The concept of well group in a special but important case captures homological properties of the zero set of a continuous map f from K to R^n on a compact space K that are invariant with respect to perturbations of f. The perturbations are arbitrary continuous maps within L_infty distance r from f for a given r > 0. The main drawback of the approach is that the computability of well groups was shown only when dim K = n or n = 1. Our contribution to the theory of well groups is twofold: on the one hand we improve on the computability issue, but on the other hand we present a range of examples where the well groups are incomplete invariants, that is, fail to capture certain important robust properties of the zero set. For the first part, we identify a computable subgroup of the well group that is obtained by cap product with the pullback of the orientation of R^n by f. In other words, well groups can be algorithmically approximated from below. When f is smooth and dim K < 2n-2, our approximation of the (dim K-n)th well group is exact. For the second part, we find examples of maps f, f' from K to R^n with all well groups isomorphic but whose perturbations have different zero sets. We discuss on a possible replacement of the well groups of vector valued maps by an invariant of a better descriptive power and computability status. AU - Franek, Peter AU - KrcΓ‘l, Marek ID - 1510 TI - On computability and triviality of well groups VL - 34 ER -