Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOn the complexity of optimal homotopies
126
0
0.0
(
0
)
Added by
Arnaud de Mesmay
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely, given two homotopic curves $gamma_1$ and $gamma_2$ on a combinatorial (say, triangulated) surface, we investigate the problem of computing a homotopy between $gamma_1$ and $gamma_2$ where the length of the longest intermediate curve is minimized. Such optimal homotopies are relevant for a wide range of purposes, from very theoretical questions in quantitative homotopy theory to more practical applications such as similarity measures on meshes and graph searching problems. We prove that Homotopy Height is in the complexity class NP, and the corresponding exponential algorithm is the best one known for this problem. This result builds on a structural theorem on monotonicity of optimal homotopies, which is proved in a companion paper. Then we show that this problem encompasses the Homotopic Frechet distance problem which we therefore also establish to be in NP, answering a question which has previously been considered in several different settings. We also provide an O(log n)-approximation algorithm for Homotopy Height on surfaces by adapting an earlier algorithm of Har-Peled, Nayyeri, Salvatipour and Sidiropoulos in the planar setting.
rate research
Read More
In the classic polyline simplification problem we want to replace a given polygonal curve $P$, consisting of $n$ vertices, by a subsequence $P$ of $k$ vertices from $P$ such that the polygonal curves $P$ and $P$ are as close as possible. Closeness is usually measured using the Hausdorff or Frechet distance. These distance measures can be applied globally, i.e., to the whole curves $P$ and $P$, or locally, i.e., to each simplified subcurve and the line segment that it was replaced with separately (and then taking the maximum). This gives rise to four problem variants: Global-Hausdorff (known to be NP-hard), Local-Hausdorff (in time $O(n^3)$), Global-Frechet (in time $O(k n^5)$), and Local-Frechet (in time $O(n^3)$). Our contribution is as follows. - Cubic time for all variants: For Global-Frechet we design an algorithm running in time $O(n^3)$. This shows that all three problems (Local-Hausdorff, Local-Frechet, and Global-Frechet) can be solved in cubic time. All these algorithms work over a general metric space such as $(mathbb{R}^d,L_p)$, but the hidden constant depends on $p$ and (linearly) on $d$. - Cubic conditional lower bound: We provide evidence that in high dimensions cubic time is essentially optimal for all three problems (Local-Hausdorff, Local-Frechet, and Global-Frechet). Specifically, improving the cubic time to $O(n^{3-epsilon} textrm{poly}(d))$ for polyline simplification over $(mathbb{R}^d,L_p)$ for $p = 1$ would violate plausible conjectures. We obtain similar results for all $p in [1,infty), p e 2$. In total, in high dimensions and over general $L_p$-norms we resolve the complexity of polyline simplification with respect to Local-Hausdorff, Local-Frechet, and Global-Frechet, by providing new algorithms and conditional lower bounds.
We study the multi-marginal partial optimal transport (POT) problem between $m$ discrete (unbalanced) measures with at most $n$ supports. We first prove that we can obtain two equivalence forms of the multimarginal POT problem in terms of the multimarginal optimal transport problem via novel extensions of cost tensor. The first equivalence form is derived under the assumptions that the total masses of each measure are sufficiently close while the second equivalence form does not require any conditions on these masses but at the price of more sophisticated extended cost tensor. Our proof techniques for obtaining these equivalence forms rely on novel procedures of moving mass in graph theory to push transportation plan into appropriate regions. Finally, based on the equivalence forms, we develop optimization algorithm, named ApproxMPOT algorithm, that builds upon the Sinkhorn algorithm for solving the entropic regularized multimarginal optimal transport. We demonstrate that the ApproxMPOT algorithm can approximate the optimal value of multimarginal POT problem with a computational complexity upper bound of the order $tilde{mathcal{O}}(m^3(n+1)^{m}/ varepsilon^2)$ where $varepsilon > 0$ stands for the desired tolerance.
Seminal works on light spanners over the years provide spanners with optimal or near-optimal lightness in various graph classes, such as in general graphs, Euclidean spanners, and minor-free graphs. Two shortcomings of all previous work on light spanners are: (1) The techniques are ad hoc per graph class, and thus cant be applied broadly (e.g., some require large stretch and are thus suitable to general graphs, while others are naturally suitable to stretch $1 + epsilon$). (2) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. This work aims at initiating a unified theory of light spanners by presenting a single framework that can be used to construct light spanners in a variety of graph classes. This theory is developed in two papers. The current paper is the first of the two -- it lays the foundations of the theory of light spanners and then applies it to design fast constructions with optimal lightness for several graph classes. Our new constructions are significantly faster than the state-of-the-art for every examined graph class; moreover, our runtimes are near-linear and usually optimal. Specifically, this paper includes the following results: (i) An $O(m alpha(m,n))$-time construction of $(2k-1)(1+epsilon)$-spanner with lightness $O(n^{1/k})$ for general graphs; (ii) An $O(nlog n)$-time construction of Euclidean $(1+epsilon)$-spanners with lightness and degree both bounded by constants in the basic algebraic computation tree (ACT) model. This construction resolves a major problem in the area of geometric spanners, which was open for three decades; (iii) An $O(nlog n)$-time construction of $(1+epsilon)$-spanners with constant lightness and degree, in the ACT model for unit disk graphs; (iv) a linear-time algorithm for constructing $(1+epsilon)$-spanners with constant lightness for minor-free graphs.
Resolving an open question from 2006, we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple $mathcal{O}(log^*n)$-round distributed algorithm that given a unit ball graph $G$ with $n$ vertices and a positive constant $epsilon < 1$ finds a $(1+epsilon)$-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the algorithm of Damian, Pandit, and Pemmaraju which runs in $mathcal{O}(log^*n)$ rounds but has a $mathcal{O}(log Delta)$ bound on its lightness, where $Delta$ is the ratio of the length of the longest edge in $G$ to the length of the shortest edge. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersection per node. This is the first distributed low-intersection topology control algorithm to the best of our knowledge. Our distributed algorithms rely on the maximal independent set algorithm of Schneider and Wattenhofer that runs in $mathcal{O}(log^*n)$ rounds of communication. If a maximal independent set is known beforehand, our algorithms run in constant number of rounds.
Let ${cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The emph{$k$-level} of ${cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${cal L}$ passing below $v$. The complexity (the maximum size) of the $k$-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(ncdot (k+1)^{1/3})$. Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$-level denotes the vertices at distance at most $k$ to a marked cell, the emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$-spheres on the sphere $mathbb{S}^d$ which are orthogonal to a set of random points on $mathbb{S}^d$. In this model, we prove that the expected complexity of the $k$-level is of order $Theta((k+1)^{d-1})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
