We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω(n2) moves are required in the worst case to tighten a contractible closed curve on a surface with non-positive Euler characteristic, where n is the number of self-intersection points. Results of Hass and Scott imply a matching O(n2) upper bound for contractible curves on orientable surfaces. Second, we prove that any closed curve on any orientable surface can be tightened as much as possible using at most O(n4) homotopy moves. Except for a few special cases, only naïve exponential upper bounds were previously known for this problem.

Sensor network localization is an instance of the NP-Hard graph realization problem. Thus, methods used in practice are not guaranteed to find the correct localization, even if it is uniquely determined by the input distances. In this article, we show the following: if the sensors are allowed to wiggle, giving us perturbed distance data, we can apply a novel algorithm to realize arbitrary Generically Globally Rigid graphs (GGR), or certain vertex subsets in non-GGR graphs whose relative positions are fixed (which include vertex sets of GGR subgraphs). And this strategy works in any dimension. In the language of structural rigidity theory, our approach corresponds to calculating the approximate kernel of a generic stress matrix for the given graph and distance data. To make our algorithm suitable for real-world applications, we also present: (i) various techniques for improving the robustness of the algorithm in the presence of measurement noise; (ii) an algorithm for detecting certain subsets of graph vertices whose relative positions are fixed in any generic realization of the graph and robustly localizing these subsets of vertices, (iii) a strategy for reducing the number of measurements needed by the algorithm. We provide simulation results of our algorithm.

Sensor network localization is an instance of the NP-HARD graph realization problem. Thus, methods used in practice are not guaranteed to find the correct localization, even if it is uniquely determined by the input distances. In this paper, we show the following: if the sensors are allowed to wiggle, giving us perturbed distance data, we can apply a novel algorithm to realize arbitrary generically globally rigid (GGR) graphs (or maximal vertex subsets in non-GGR graphs whose relative positions are fixed). And this algorithm works in any dimension. In the language of structural rigidity theory, our approach corresponds to calculating the approximate kernel of a generic stress matrix for the given graph and distance data. To make our algorithm suitable for real-world application, we present techniques for improving the robustness of the algorithm under noisy measurements, and a strategy for reducing the required number of measurements.