5 Search Results for "Newsam, Shawn"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.36
Faster Fréchet Distance Under Transformations

Authors: Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
We study the problem of computing the Fréchet distance between two polygonal curves under transformations. First, we consider translations in the Euclidean plane. Given two curves π and σ of total complexity n and a threshold δ ≥ 0, we present an 𝒪̃(n^{7 + 1/3}) time algorithm to determine whether there exists a translation t ∈ ℝ² such that the Fréchet distance between π and σ + t is at most δ. This improves on the previous best result, which is an 𝒪(n⁸) time algorithm. We then generalize this result to any class of rationally parameterized transformations, which includes translation, rotation, scaling, and arbitrary affine transformations. For a class T of rationally parametrized transformations with k degrees of freedom, we show that one can determine whether there is a transformation τ ∈ T such that the Fréchet distance between π and τ(σ) is at most δ in 𝒪̃(n^{3k+4/3}) time.
Cite as

Kevin Buchin, Maike Buchin, Zijin Huang, André Nusser, and Sampson Wong. Faster Fréchet Distance Under Transformations. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 36:1-36:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ICALP.2025.36,
  author =	{Buchin, Kevin and Buchin, Maike and Huang, Zijin and Nusser, Andr\'{e} and Wong, Sampson},
  title =	{{Faster Fr\'{e}chet Distance Under Transformations}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{36:1--36:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.36},
  URN =		{urn:nbn:de:0030-drops-234137},
  doi =		{10.4230/LIPIcs.ICALP.2025.36},
  annote =	{Keywords: Fr\'{e}chet distance, curve similarity, shape matching}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.54
The Fréchet Distance Unleashed: Approximating a Dog with a Frog

Authors: Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We show that a variant of the continuous Fréchet distance between polygonal curves can be computed using essentially the same algorithm used to solve the discrete version. The new variant is not necessarily monotone, but this shortcoming can be easily handled via refinement. Combined with a Dijkstra/Prim type algorithm, this leads to a realization of the Fréchet distance (i.e., a morphing) that is locally optimal (aka locally correct), that is both easy to compute, and in practice, takes near linear time on many inputs. The new morphing has the property that the leash is always as short as possible. These matchings/morphings are more natural, and are better than the ones computed by standard algorithms - in particular, they handle noise more graciously. This should make the Fréchet distance more useful for real world applications. We implemented the new algorithm, and various strategies to obtain fast practical performance. We performed extensive experiments with our new algorithm, and released publicly available (and easily installable and usable) Julia and Python packages. In particular, the Julia implementation, for computing the regular Fréchet distance, seems to be {significantly faster} than other currently available implementations. See Table 2.2. Our algorithms can be used to compute the almost-exact Fréchet distance between polygonal curves. Implementations and numerous examples are available here: https://frechet.xyz.
Cite as

Sariel Har-Peled, Benjamin Raichel, and Eliot W. Robson. The Fréchet Distance Unleashed: Approximating a Dog with a Frog. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 54:1-54:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{harpeled_et_al:LIPIcs.SoCG.2025.54,
  author =	{Har-Peled, Sariel and Raichel, Benjamin and Robson, Eliot W.},
  title =	{{The Fr\'{e}chet Distance Unleashed: Approximating a Dog with a Frog}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{54:1--54:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.54},
  URN =		{urn:nbn:de:0030-drops-232066},
  doi =		{10.4230/LIPIcs.SoCG.2025.54},
  annote =	{Keywords: Curve similarity, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.22
Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D

Authors: Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, and Marena Richter

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The Fréchet distance is a computational mainstay for comparing polygonal curves. The Fréchet distance under translation, which is a translation invariant version, considers the similarity of two curves independent of their location in space. It is defined as the minimum Fréchet distance that arises from allowing arbitrary translations of the input curves. This problem and numerous variants of the Fréchet distance under some transformations have been studied, with more work concentrating on the discrete Fréchet distance, leaving a significant gap between the discrete and continuous versions of the Fréchet distance under transformations. Our contribution is twofold: First, we present an algorithm for the Fréchet distance under translation on 1-dimensional curves of complexity n with a running time of 𝒪(n^{8/3} log³ n). To achieve this, we develop a novel framework for the problem for 1-dimensional curves, which also applies to other scenarios and leads to our second contribution. We present an algorithm with the same running time of 𝒪(n^{8/3} log³ n) for the Fréchet distance under scaling for 1-dimensional curves. For both algorithms we match the running times of the discrete case and improve the previously best known bounds of 𝒪̃(n⁴). Our algorithms rely on technical insights but are conceptually simple, essentially reducing the continuous problem to the discrete case across different length scales.
Cite as

Lotte Blank, Jacobus Conradi, Anne Driemel, Benedikt Kolbe, André Nusser, and Marena Richter. Transforming Dogs on the Line: On the Fréchet Distance Under Translation or Scaling in 1D. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 22:1-22:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.SoCG.2025.22,
  author =	{Blank, Lotte and Conradi, Jacobus and Driemel, Anne and Kolbe, Benedikt and Nusser, Andr\'{e} and Richter, Marena},
  title =	{{Transforming Dogs on the Line: On the Fr\'{e}chet Distance Under Translation or Scaling in 1D}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{22:1--22:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.22},
  URN =		{urn:nbn:de:0030-drops-231746},
  doi =		{10.4230/LIPIcs.SoCG.2025.22},
  annote =	{Keywords: Fr\'{e}chet distance under translation, Fr\'{e}chet distance under scaling, time series, shape matching}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.41
Residue Domination in Bounded-Treewidth Graphs

Authors: Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
For the vertex selection problem (σ,ρ)-DomSet one is given two fixed sets σ and ρ of integers and the task is to decide whether we can select vertices of the input graph such that, for every selected vertex, the number of selected neighbors is in σ and, for every unselected vertex, the number of selected neighbors is in ρ [Telle, Nord. J. Comp. 1994]. This framework covers many fundamental graph problems such as Independent Set and Dominating Set. We significantly extend the recent result by Focke et al. [SODA 2023] to investigate the case when σ and ρ are two (potentially different) residue classes modulo m ≥ 2. We study the problem parameterized by treewidth and present an algorithm that solves in time m^tw ⋅ n^O(1) the decision, minimization and maximization version of the problem. This significantly improves upon the known algorithms where for the case m ≥ 3 not even an explicit running time is known. We complement our algorithm by providing matching lower bounds which state that there is no (m-ε)^pw ⋅ n^O(1)-time algorithm parameterized by pathwidth pw, unless SETH fails. For m = 2, we extend these bounds to the minimization version as the decision version is efficiently solvable.
Cite as

Jakob Greilhuber, Philipp Schepper, and Philip Wellnitz. Residue Domination in Bounded-Treewidth Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{greilhuber_et_al:LIPIcs.STACS.2025.41,
  author =	{Greilhuber, Jakob and Schepper, Philipp and Wellnitz, Philip},
  title =	{{Residue Domination in Bounded-Treewidth Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{41:1--41:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.41},
  URN =		{urn:nbn:de:0030-drops-228675},
  doi =		{10.4230/LIPIcs.STACS.2025.41},
  annote =	{Keywords: Parameterized Complexity, Treewidth, Generalized Dominating Set, Strong Exponential Time Hypothesis}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.3
Generalizing Deep Models for Overhead Image Segmentation Through Getis-Ord Gi* Pooling

Authors: Xueqing Deng, Yuxin Tian, and Shawn Newsam

Published in: LIPIcs, Volume 177, 11th International Conference on Geographic Information Science (GIScience 2021) - Part I (2020)

Abstract
That most deep learning models are purely data driven is both a strength and a weakness. Given sufficient training data, the optimal model for a particular problem can be learned. However, this is usually not the case and so instead the model is either learned from scratch from a limited amount of training data or pre-trained on a different problem and then fine-tuned. Both of these situations are potentially suboptimal and limit the generalizability of the model. Inspired by this, we investigate methods to inform or guide deep learning models for geospatial image analysis to increase their performance when a limited amount of training data is available or when they are applied to scenarios other than which they were trained on. In particular, we exploit the fact that there are certain fundamental rules as to how things are distributed on the surface of the Earth and these rules do not vary substantially between locations. Based on this, we develop a novel feature pooling method for convolutional neural networks using Getis-Ord Gi* analysis from geostatistics. Experimental results show our proposed pooling function has significantly better generalization performance compared to a standard data-driven approach when applied to overhead image segmentation.
Cite as

Xueqing Deng, Yuxin Tian, and Shawn Newsam. Generalizing Deep Models for Overhead Image Segmentation Through Getis-Ord Gi* Pooling. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{deng_et_al:LIPIcs.GIScience.2021.I.3,
  author =	{Deng, Xueqing and Tian, Yuxin and Newsam, Shawn},
  title =	{{Generalizing Deep Models for Overhead Image Segmentation Through Getis-Ord Gi* Pooling}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-166-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{177},
  editor =	{Janowicz, Krzysztof and Verstegen, Judith A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2021.I.3},
  URN =		{urn:nbn:de:0030-drops-130387},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.3},
  annote =	{Keywords: Remote sensing, convolutional neural networks, pooling function, semantic segmentation, generalization}
}
  • Refine by Type
  • 5 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2020

  • Refine by Author
  • 2 Nusser, André
  • 1 Blank, Lotte
  • 1 Buchin, Kevin
  • 1 Buchin, Maike
  • 1 Conradi, Jacobus
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Computational geometry
  • 1 Computing methodologies → Neural networks
  • 1 Theory of computation → Parameterized complexity and exact algorithms

  • Refine by Keyword
  • 2 Fréchet distance
  • 2 shape matching
  • 1 Curve similarity
  • 1 Fréchet distance under scaling
  • 1 Fréchet distance under translation
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact