903 research outputs found
Bicriteria Approximation for Minimum Dilation Graph Augmentation
No full textSpanner constructions focus on the initial design of the network. However, networks tend to improve over time. In this paper, we focus on the improvement step. Given a graph and a budget k, which k edges do we add to the graph to minimise its dilation? Gudmundsson and Wong [TALG'22] provided the first positive result for this problem, but their approximation factor is linear in k.
Our main result is a (2 √[r]{2} k^{1/r},2r)-bicriteria approximation that runs in O(n³ log n) time, for all r ≥ 1. In other words, if t^* is the minimum dilation after adding any k edges to a graph, then our algorithm adds O(k^{1+1/r}) edges to the graph to obtain a dilation of 2rt^*. Moreover, our analysis of the algorithm is tight under the Erdős girth conjecture
On the hardness of computing an average curve
No full textWe study the complexity of clustering curves under k-median and k-center objectives in the metric space of the Fréchet distance and related distance measures. The k-center problem has recently been shown to be NP-hard, even in the case where k=1, i.e. the minimum enclosing ball under the Fréchet distance. We extend these results by showing that also the k-median problem is NP-hard for k=1. Furthermore, we show that the 1-median problem is W[1]-hard with the number of curves as parameter. We show this under the discrete and continuous Fréchet and Dynamic Time Warping (DTW) distance. Our result generalizes an earlier result by Bulteau et al. from 2018 for a variant of DTW that uses squared distances. Moreover, closing some gaps in the literature, we show positive results for a variant where the center curve may have complexity at most ℓ under the discrete Fréchet distance. In particular, for fixed k,ℓ and ε, we give (1+ε)-approximation algorithms for the (k,ℓ)-median and (k,ℓ)-center objectives and a polynomial-time exact algorithm for the (k,ℓ)-center objective
The k-Fréchet Distance: How to Walk Your Dog While Teleporting
No full textWe introduce a new distance measure for comparing polygonal chains: the k-Fréchet distance. As the name implies, it is closely related to the well-studied Fréchet distance but detects similarities between curves that resemble each other only piecewise. The parameter k denotes the number of subcurves into which we divide the input curves (thus we allow up to k-1 "teleports" on each input curve). The k-Fréchet distance provides a nice transition between (weak) Fréchet distance and Hausdorff distance. However, we show that deciding this distance measure turns out to be NP-hard, which is interesting since both (weak) Fréchet and Hausdorff distance are computable in polynomial time. Nevertheless, we give several possibilities to deal with the hardness of the k-Fréchet distance: besides a short exponential-time algorithm for the general case, we give a polynomial-time algorithm for k=2, i.e., we ask that we subdivide our input curves into two subcurves each. We can also approximate the optimal k by factor 2. We then present a more intricate FPT algorithm using parameters k (the number of allowed subcurves) and z (the number of segments of one curve that intersect the epsilon-neighborhood of a point on the other curve)
Geometric Spanners of Bounded Tree-Width
No full textGiven a point set P in the Euclidean space, a geometric t-spanner G is a graph on P such that for every pair of points, the shortest path in G between those points is at most a factor t longer than the Euclidean distance between those points. The value t ≥ 1 is called the dilation of G. Commonly, the aim is to construct a t-spanner with additional desirable properties. In graph theory, a powerful tool to admit efficient algorithms is bounded tree-width. We therefore investigate the problem of computing geometric spanners with bounded tree-width and small dilation t.
Let d be a fixed integer and P ⊂ ℝ^d be a point set with n points. We give a first algorithm to compute an (n/k^{d/(d-1)})-spanner on P with tree-width at most k. The dilation obtained by the algorithm is asymptotically worst-case optimal for graphs with tree-width k: We show that there is a set of n points such that every spanner of tree-width k has dilation (n/k^{d/(d-1)}). We further prove a tight dependency between tree-width and the number of edges in sparse connected planar graphs, which admits, for point sets in ℝ², a plane spanner with tree-width at most k and small maximum vertex degree.
Finally, we show an almost tight bound on the minimum dilation of a spanning tree of n equally spaced points on a circle
Reprint of : Memory-constrained algorithms for simple polygons
No full textA constant-work-space algorithm has read-only access to an input array and may use only O(1) additional words of bits, where n is the input size. We show how to triangulate a plane straight-line graph with n vertices in O(n2) time and constant work-space. We also consider the problem of preprocessing a simple polygon P for shortest path queries, where P is given by the ordered sequence of its n vertices. For this, we relax the space constraint to allow s words of work-space. After quadratic preprocessing, the shortest path between any two points inside P can be found in O(n2/s) time.
Keywords: Space–time trade-off; Constant workspace; Triangulation; Shortest path; Simple polygon
Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, André Schulz
Memory-constrained algorithms for simple polygons
Computational Geometry, Volume 46, Issue 8, October 2013, Pages 959-969
http://dx.doi.org/10.1016/j.comgeo.2013.04.00
A Spanner for the Day After
No full textWe show how to construct (1+epsilon)-spanner over a set P of n points in R^d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters theta, epsilon in (0,1), the computed spanner G has O(epsilon^{-7d} log^7 epsilon^{-1} * theta^{-6} n log n (log log n)^6) edges. Furthermore, for any k, and any deleted set B subseteq P of k points, the residual graph G \ B is (1+epsilon)-spanner for all the points of P except for (1+theta)k of them. No previous constructions, beyond the trivial clique with O(n^2) edges, were known such that only a tiny additional fraction (i.e., theta) lose their distance preserving connectivity.
Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one dimensional construction in a black box fashion
Rolling block mazes are PSPACE-complete
No full textIn a rolling block maze, one or more blocks lie on a rectangular board with square cells. In most mazes, the blocks have size k × m × n where k, m, n are integers that determine the size of the block in terms of units of the size of the board cells. The task of a rolling block maze is to roll a particular block from a starting to an ending placement. A block is rolled by tipping it over one of its edges. Some of the squares of the board are marked as forbidden to roll on. We show that solving rolling block mazes is PSPACE-complete
Fine-Grained Complexity Analysis of Two Classic TSP Variants
No full textWe analyze two classic variants of the Traveling Salesman Problem using the toolkit of fine-grained complexity.
Our first set of results is motivated by the Bitonic tsp problem: given a set of n points in the plane, compute a shortest tour consisting of two monotone chains. It is a classic dynamicprogramming exercise to solve this problem in O(n^2) time. While the near-quadratic dependency of similar dynamic programs for Longest Common Subsequence and Discrete Fréchet Distance has recently been proven to be essentially optimal under the Strong Exponential Time Hypothesis, we show that bitonic tours can be found in subquadratic time. More precisely, we present an algorithm that solves bitonic tsp in O(n*log^2(n)) time and its bottleneck version in O(n*log^3(n)) time. In the more general pyramidal tsp problem, the points to be visited are labeled 1, ..., n and the sequence of labels in the solution is required to have at most one local maximum. Our algorithms for the bitonic (bottleneck) tsp problem also work for the pyramidal tsp problem in the plane.
Our second set of results concerns the popular k-opt heuristic for tsp in the graph setting. More precisely, we study the k-opt decision problem, which asks whether a given tour can be improved by a k-opt move that replaces k edges in the tour by k new edges. A simple algorithm solves k-opt in O(n^k) time for fixed k. For 2-opt, this is easily seen to be optimal. For k = 3 we prove that an algorithm with a runtime of the form ~O(n^{3-epsilon}) exists if and only if All-Pairs Shortest Paths in weighted digraphs has such an algorithm. For general k-opt, it is known that a runtime of f(k)*n^{o(k/log(k))} would contradict the Exponential Time Hypothesis. The results for k = 2, 3 may suggest that the actual time complexity of k-opt is Theta(n^k). We show that this is not the case, by presenting an algorithm that finds the best k-move in O(n^{lfoor 2k/3 rfloor +1}) time for fixed k >= 3. This implies that 4-opt can be solved in O(n^3) time, matching the best-known algorithm for 3-opt. Finally, we show how to beat the quadratic barrier for k = 2 in two important settings, namely for points in the plane and when we want to solve 2-opt repeatedl
Computing Continuous Dynamic Time Warping of Time Series in Polynomial Time
No full textDynamic Time Warping is arguably the most popular similarity measure for time
series, where we define a time series to be a one-dimensional polygonal curve.
The drawback of Dynamic Time Warping is that it is sensitive to the sampling
rate of the time series. The Fr\'echet distance is an alternative that has
gained popularity, however, its drawback is that it is sensitive to outliers.
Continuous Dynamic Time Warping (CDTW) is a recently proposed alternative
that does not exhibit the aforementioned drawbacks. CDTW combines the
continuous nature of the Fr\'echet distance with the summation of Dynamic Time
Warping, resulting in a similarity measure that is robust to sampling rate and
to outliers. In a recent experimental work of Brankovic et al., it was
demonstrated that clustering under CDTW avoids the unwanted artifacts that
appear when clustering under Dynamic Time Warping and under the Fr\'echet
distance. Despite its advantages, the major shortcoming of CDTW is that there
is no exact algorithm for computing CDTW, in polynomial time or otherwise.
In this work, we present the first exact algorithm for computing CDTW of
one-dimensional curves. Our algorithm runs in time for a pair of
one-dimensional curves, each with complexity at most . In our algorithm, we
propagate continuous functions in the dynamic program for CDTW, where the main
difficulty lies in bounding the complexity of the functions. We believe that
our result is an important first step towards CDTW becoming a practical
similarity measure between curves.Comment: In SoCG 202
{O}(k)-robust spanners in one dimension
No full textA geometric t-spanner on a set of points in Euclidean space is a graph containing for every pair of points a path of length at most t times the Euclidean distance between the points. Informally, a spanner is O(k)-robust if deleting k vertices only harms O(k) other vertices. We show that on any one-dimensional set of n points, for any ε>0, there exists an O(k)-robust 1-spanner with O(n1+ε) edges. Previously it was only known that O(k)-robust spanners with O(n2) edges exists and that there are point sets on which any O(k)-robust spanner has Ω(nlogn) edges
- …
