More Like this

1. Fast Fréchet Distance for Curves with Long Edges

   Gudmundsson, J. ; Mirzanezhad, M. ; Mohades, A. ; Wenk, C. ( April 2018 , 3rd International Workshop on Interactive and Spatial Computing)

   Computing Fréchet distance between two curves takes roughly quadratic time. The only strongly subquadratic time algorithm has been proposed in [7] for c-packed curves. In this paper, we show that for curves with long edges the Fréchet distance computations become easier. Let P and Q be two polygonal curves in Rd with n and m vertices, respectively. We prove three main results for the case when all edges of both curves are long compared to the Fréchet distance between them: (1) a linear-time algorithm for deciding the Fréchet distance between two curves, (2) an algorithm that computes the Fréchet distance in O((n + m) log(n + m)) time, and (3) a linear-time [EQUATION]-approximation algorithm for approximating the Fréchet distance between two curves. 

   more » « less
2. Subtrajectory Clustering: Finding Set Covers for Set Systems of Subcurves

   Brüning, F. ; Akitaya, H. ; Chambers, E ; Driemel, A ( February 2023 , Computing in geometry and topology)

   We study subtrajectory clustering under the Fréchet distance. Given one or more trajectories, the task is to split the trajectories into several parts, such that the parts have a good clustering structure. We approach this problem via a new set cover formulation, which we think provides a natural formalization of the problem as it is studied in many applications. Given a polygonal curve P with n vertices in fixed dimension, integers k, ℓ ≥ 1, and a real value Δ > 0, the goal is to find k center curves of complexity at most ℓ such that every point on P is covered by a subtrajectory that has small Fréchet distance to one of the k center curves (≤ Δ). In many application scenarios, one is interested in finding clusters of small complexity, which is controlled by the parameter ℓ. Our main result is a bicriterial approximation algorithm: if there exists a solution for given parameters k, ℓ, and Δ, then our algorithm finds a set of k' center curves of complexity at most ℓ with covering radius Δ' with k' in O(kℓ2 log (kℓ)), and Δ' ≤ 19Δ. Moreover, within these approximation bounds, we can minimize k while keeping the other parameters fixed. If ℓ is a constant independent of n, then, the approximation factor for the number of clusters k is O(log k) and the approximation factor for the radius Δ is constant. In this case, the algorithm has expected running time in Õ(km2 + mn) and uses space in O(n + m), where m=⌈L/Δ⌉ and L is the total arclength of the curve P. 

   more » « less
3. Fréchet Distance for Uncertain Curves

   https://doi.org/10.1145/3597640  

   Buchin, Kevin ; Fan, Chenglin ; Löffler, Maarten ; Popov, Aleksandr ; Raichel, Benjamin ; Roeloffzen, Marcel ( July 2023 , ACM Transactions on Algorithms)

   In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #P-hard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly δ-separated convex regions. Finally, we study the setting with Sakoe–Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets. 

   more » « less
4. Why Is Maximum Clique Often Easy in Practice?

   https://doi.org/10.1287/opre.2019.1970  

   Walteros, Jose L. ; Buchanan, Austin ( November 2020 , Operations Research)

   null (Ed.)

   To this day, the maximum clique problem remains a computationally challenging problem. Indeed, despite researchers’ best efforts, there exist unsolved benchmark instances with 1,000 vertices. However, relatively simple algorithms solve real-life instances with millions of vertices in a few seconds. Why is this the case? Why is the problem apparently so easy in many naturally occurring networks? In this paper, we provide an explanation. First, we observe that the graph’s clique number ω is very near to the graph’s degeneracy d in most real-life instances. This observation motivates a main contribution of this paper, which is an algorithm for the maximum clique problem that runs in time polynomial in the size of the graph, but exponential in the gap [Formula: see text] between the clique number ω and its degeneracy-based upper bound d+1. When this gap [Formula: see text] can be treated as a constant, as is often the case for real-life graphs, the proposed algorithm runs in time [Formula: see text]. This provides a rigorous explanation for the apparent easiness of these instances despite the intractability of the problem in the worst case. Further, our implementation of the proposed algorithm is actually practical—competitive with the best approaches from the literature. 

   more » « less
5. Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Directed Network Design Problems

   https://doi.org/10.1287/moor.2021.1181  

   Ghuge, Rohan ; Nagarajan, Viswanath ( May 2022 , Mathematics of Operations Research)

   We consider the following general network design problem. The input is an asymmetric metric (V, c), root [Formula: see text], monotone submodular function [Formula: see text], and budget B. The goal is to find an r-rooted arborescence T of cost at most B that maximizes f(T). Our main result is a simple quasi-polynomial time [Formula: see text]-approximation algorithm for this problem, in which [Formula: see text] is the number of vertices in an optimal solution. As a consequence, we obtain an [Formula: see text]-approximation algorithm for directed (polymatroid) Steiner tree in quasi-polynomial time. We also extend our main result to a setting with additional length bounds at vertices, which leads to improved [Formula: see text]-approximation algorithms for the single-source buy-at-bulk and priority Steiner tree problems. For the usual directed Steiner tree problem, our result matches the best previous approximation ratio but improves significantly on the running time. For polymatroid Steiner tree and single-source buy-at-bulk, our result improves prior approximation ratios by a logarithmic factor. For directed priority Steiner tree, our result seems to be the first nontrivial approximation ratio. Under certain complexity assumptions, our approximation ratios are the best possible (up to constant factors). 

   more » « less