More Like this

1. Fréchet Edit Distance

   https://doi.org/10.4230/LIPIcs.SoCG.2024.58  

   Fox, Emily ; Nayyeri, Amir ; Perry, Jonathan James ; Raichel, Benjamin ( June 2024 , Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mulzer, Wolfgang ; Phillips, Jeff M (Ed.)

   We define and investigate the Fréchet edit distance problem. Given two polygonal curves π and σ and a non-negative threshhold value δ, we seek the minimum number of edits to σ such that the Fréchet distance between the edited σ and π is at most δ. For the edit operations we consider three cases, namely, deletion of vertices, insertion of vertices, or both. For this basic problem we consider a number of variants. Specifically, we provide polynomial time algorithms for both discrete and continuous Fréchet edit distance variants, as well as hardness results for weak Fréchet edit distance variants. 

   more » « less
2. Fast Fréchet Distance Between Curves with Long Edges

   https://doi.org/10.1142/S0218195919500043  

   Gudmundsson, Joachim ; Mirzanezhad, Majid ; Mohades, Ali ; Wenk, Carola ( June 2019 , International Journal of Computational Geometry & Applications)

   Computing the Fréchet distance between two polygonal curves takes roughly quadratic time. In this paper, we show that for a special class of curves the Fréchet distance computations become easier. Let [Formula: see text] and [Formula: see text] be two polygonal curves in [Formula: see text] with [Formula: see text] and [Formula: see text] vertices, respectively. We prove four 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 [Formula: see text] time, (3) a linear-time [Formula: see text]-approximation algorithm, and (4) a data structure that supports [Formula: see text]-time decision queries, where [Formula: see text] is the number of vertices of the query curve and [Formula: see text] the number of vertices of the preprocessed curve. 

   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. 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
5. All-or-Nothing Phenomena: From Single-Letter to High Dimensions

   https://doi.org/10.1109/CAMSAP45676.2019.9022473  

   Reeves, Galen ; Xu, Jiaming ; Zadik, Ilias ( December 2019 , 2019 IEEE 8th International Workshop on Computational Advances in Multi-Sensor Adaptive Processing (CAMSAP))

   We consider the problem of estimating a $p$ -dimensional vector $\beta$ from $n$ observations $Y=X\beta+W$ , where $\beta_{j}\mathop{\sim}^{\mathrm{i.i.d}.}\pi$ for a real-valued distribution $\pi$ with zero mean and unit variance’ $X_{ij}\mathop{\sim}^{\mathrm{i.i.d}.}\mathcal{N}(0,1)$ , and $W_{i}\mathop{\sim}^{\mathrm{i.i.d}.}\mathcal{N}(0,\ \sigma^{2})$ . In the asymptotic regime where $n/p\rightarrow\delta$ and $p/\sigma^{2}\rightarrow$ snr for two fixed constants $\delta,\ \mathsf{snr}\in(0,\ \infty)$ as $p\rightarrow\infty$ , the limiting (normalized) minimum mean-squared error (MMSE) has been characterized by a single-letter (additive Gaussian scalar) channel. In this paper, we show that if the MMSE function of the single-letter channel converges to a step function, then the limiting MMSE of estimating $\beta$ converges to a step function which jumps from 1 to 0 at a critical threshold. Moreover, we establish that the limiting mean-squared error of the (MSE-optimal) approximate message passing algorithm also converges to a step function with a larger threshold, providing evidence for the presence of a computational-statistical gap between the two thresholds. 

   more » « less