DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2026.116

Dimension Reduction for Curves: Simplified and Generalized

Authors: Matthijs Ebbens, Jie Lu, and Alexander Munteanu

Published in: LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026)

Abstract

We revisit random projections for reducing the dimension of high-dimensional polygonal curves. Drawing from the toolbox of randomized linear algebra, we give a considerably simplified proof of the known O(ε^{-2} log(nm)) bound on the target dimension of a random projection that preserves the continuous Fréchet distance of polygonal curves up to a factor (1±ε). Our proof is based on the concept of sparse oblivious subspace embeddings. While previous techniques were limited to the case of the Fréchet distance, our techniques are fairly general and extend to all possible distance measures that involve the maximum, a sum or an integral over Euclidean distances between pairs of points on both input curves. We define a generalized dissimilarity measure for curves that includes several popular measures such as Fréchet, q-DTW, Hausdorff, etc. as special cases and show that the same dimension reduction technique works for this generalized dissimilarity measure. Finally, we apply the same framework for dimension reduction to piecewise linear surfaces, after extending the distance measure suitably to such surfaces.

Cite as

Matthijs Ebbens, Jie Lu, and Alexander Munteanu. Dimension Reduction for Curves: Simplified and Generalized. In 34th Annual European Symposium on Algorithms (ESA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 388, pp. 116:1-116:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ebbens_et_al:LIPIcs.ESA.2026.116,
  author =	{Ebbens, Matthijs and Lu, Jie and Munteanu, Alexander},
  title =	{{Dimension Reduction for Curves: Simplified and Generalized}},
  booktitle =	{34th Annual European Symposium on Algorithms (ESA 2026)},
  pages =	{116:1--116:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-445-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{388},
  editor =	{Bille, Philip and Pettie, Seth and Storandt, Sabine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.116},
  URN =		{urn:nbn:de:0030-drops-272521},
  doi =		{10.4230/LIPIcs.ESA.2026.116},
  annote =	{Keywords: dimension reduction, Fr\'{e}chet distance, dynamic time warping, polygonal curves, piecewise linear surfaces}
}

Search Results

Documents authored by Lu, Jie

Dimension Reduction for Curves: Simplified and Generalized

Abstract

Cite as

Thanks for your feedback!

Could not send message