Search Results

Documents authored by Driemel, Anne

Document
DOI: 10.4230/LIPIcs.ESA.2024.28
A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case

Authors: Lotte Blank and Anne Driemel

Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)

Abstract
The fine-grained complexity of computing the {Fréchet distance } has been a topic of much recent work, starting with the quadratic SETH-based conditional lower bound by Bringmann from 2014. Subsequent work established largely the same complexity lower bounds for the {Fréchet distance } in 1D. However, the imbalanced case, which was shown by Bringmann to be tight in dimensions d ≥ 2, was still left open. Filling in this gap, we show that a faster algorithm for the {Fréchet distance } in the imbalanced case is possible: Given two 1-dimensional curves of complexity n and n^{α} for some α ∈ (0,1), we can compute their {Fréchet distance } in O(n^{2α} log² n + n log n) time. This rules out a conditional lower bound of the form O((nm)^{1-ε}) that Bringmann showed for d ≥ 2 and any ε > 0 in turn showing a strict separation with the setting d = 1. At the heart of our approach lies a data structure that stores a 1-dimensional curve P of complexity n, and supports queries with a curve Q of complexity m for the continuous {Fréchet distance } between P and Q. The data structure has size in 𝒪(nlog n) and uses query time in 𝒪(m² log² n). Our proof uses a key lemma that is based on the concept of visiting orders and may be of independent interest. We demonstrate this by substantially simplifying the correctness proof of a clustering algorithm by Driemel, Krivošija and Sohler from 2015.
Cite as

Lotte Blank and Anne Driemel. A Faster Algorithm for the Fréchet Distance in 1D for the Imbalanced Case. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.ESA.2024.28,
  author =	{Blank, Lotte and Driemel, Anne},
  title =	{{A Faster Algorithm for the Fr\'{e}chet Distance in 1D for the Imbalanced Case}},
  booktitle =	{32nd Annual European Symposium on Algorithms (ESA 2024)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-338-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{308},
  editor =	{Chan, Timothy and Fischer, Johannes and Iacono, John and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2024.28},
  URN =		{urn:nbn:de:0030-drops-210999},
  doi =		{10.4230/LIPIcs.ESA.2024.28},
  annote =	{Keywords: \{Fr\'{e}chet distance\}, distance oracle, data structures, time series}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.15
Range Reporting for Time Series via Rectangle Stabbing

Authors: Lotte Blank and Anne Driemel

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
We study the Fréchet queries problem. It is a data structure problem for range reporting, where we are given a set S of n polygonal curves and a distance threshold ρ. The data structure should support queries with a polygonal curve q for the elements of S, for which the continuous Fréchet distance to q is at most ρ. Afshani and Driemel in 2018 studied this problem for two-dimensional polygonal curves of constant complexity and gave upper and lower bounds on the space-query time tradeoff. We study the case that the ambient space of the curves is one-dimensional and show an intimate connection to the well-studied rectangle stabbing problem. Here, we are given a set of hyperrectangles as input and a query with a point q should return all input rectangles that contain this point. Using known data structures for rectangle stabbing or orthogonal range searching this directly leads to a data structure with size in 𝒪(n log^{t-1} n) and query time in 𝒪(log^{t-1} n+k), where k denotes the output size and t can be chosen as the maximum number of vertices of either (a) the stored curves or (b) the query curves. Note that we omit factors depending on the complexity of the curves that do not depend on n. The resulting bounds improve upon the bounds by Afshani and Driemel in both the storage and query time. In addition, we show that known lower bounds for rectangle stabbing and orthogonal range reporting with dimension parameter d = ⌊t/2⌋ can be applied to our problem via reduction.
Cite as

Lotte Blank and Anne Driemel. Range Reporting for Time Series via Rectangle Stabbing. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blank_et_al:LIPIcs.SWAT.2024.15,
  author =	{Blank, Lotte and Driemel, Anne},
  title =	{{Range Reporting for Time Series via Rectangle Stabbing}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{15:1--15:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.15},
  URN =		{urn:nbn:de:0030-drops-200559},
  doi =		{10.4230/LIPIcs.SWAT.2024.15},
  annote =	{Keywords: Data Structures, Fr\'{e}chet distance, Rectangle Stabbing, Orthogonal Range Searching}
}
Document
DOI: 10.4230/DagRep.13.8.91
Computational Geometry of Earth System Analysis (Dagstuhl Seminar 23342)

Authors: Susanne Crewell, Anne Driemel, Jeff M. Phillips, and Dwaipayan Chatterjee

Published in: Dagstuhl Reports, Volume 13, Issue 8 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 23342 "Computational Geometry of Earth System Analysis". This seminar brought together experts of algorithms and the Earth sciences to foster collaborations that can tackle algorithmic problems in the Earth system by the crossover of expertise in these different areas. The Earth sciences include a manifold of disciplines that deal with atmospheric, oceanic and terrestrial observations to further our understanding of climate processes. New generations of observation systems that are being developed right now provide novel data about the atmospheric and surface conditions at increasing spatial and temporal resolution. This provides unique information to improve weather and climate prediction but cannot always be handled by traditional numerical models. Computational Geometry is rooted in a strong tradition of algorithm and complexity analysis applied to practical geometric problems. Efficient algorithmic methods developed in this field are often tailored to the low-dimensional geometric settings that arise in a multitude of application areas, but have until recently not been applied to problems arising in the Earth system sciences - and in particular not in meteorology.
Cite as

Susanne Crewell, Anne Driemel, Jeff M. Phillips, and Dwaipayan Chatterjee. Computational Geometry of Earth System Analysis (Dagstuhl Seminar 23342). In Dagstuhl Reports, Volume 13, Issue 8, pp. 91-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{crewell_et_al:DagRep.13.8.91,
  author =	{Crewell, Susanne and Driemel, Anne and Phillips, Jeff M. and Chatterjee, Dwaipayan},
  title =	{{Computational Geometry of Earth System Analysis (Dagstuhl Seminar 23342)}},
  pages =	{91--105},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{13},
  number =	{8},
  editor =	{Crewell, Susanne and Driemel, Anne and Phillips, Jeff M. and Chatterjee, Dwaipayan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.8.91},
  URN =		{urn:nbn:de:0030-drops-198147},
  doi =		{10.4230/DagRep.13.8.91},
  annote =	{Keywords: Data reduction, Event detection, Feature tracking, Geometric algorithms, Interpolation methods, Sensor placement}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.28
Faster Approximate Covering of Subcurves Under the Fréchet Distance

Authors: Frederik Brüning, Jacobus Conradi, and Anne Driemel

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Subtrajectory clustering is an important variant of the trajectory clustering problem, where the start and endpoints of trajectory patterns within the collected trajectory data are not known in advance. We study this problem in the form of a set cover problem for a given polygonal curve: find the smallest number k of representative curves such that any point on the input curve is contained in a subcurve that has Fréchet distance at most a given Δ to a representative curve. We focus on the case where the representative curves are line segments and approach this NP-hard problem with classical techniques from the area of geometric set cover: we use a variant of the multiplicative weights update method which was first suggested by Brönniman and Goodrich for set cover instances with small VC-dimension. We obtain a bicriteria-approximation algorithm that computes a set of O(klog(k)) line segments that cover a given polygonal curve of n vertices under Fréchet distance at most O(Δ). We show that the algorithm runs in Õ(k² n + k n³) time in expectation and uses Õ(k n + n³) space. For input curves that are c-packed and lie in the plane, we bound the expected running time by Õ(k² c² n) and the space by Õ(kn + c² n). In addition, we present a variant of the algorithm that uses implicit weight updates on the candidate set and thereby achieves near-linear running time in n without any assumptions on the input curve, while keeping the same approximation bounds. This comes at the expense of a small (polylogarithmic) dependency on the relative arclength.
Cite as

Frederik Brüning, Jacobus Conradi, and Anne Driemel. Faster Approximate Covering of Subcurves Under the Fréchet Distance. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bruning_et_al:LIPIcs.ESA.2022.28,
  author =	{Br\"{u}ning, Frederik and Conradi, Jacobus and Driemel, Anne},
  title =	{{Faster Approximate Covering of Subcurves Under the Fr\'{e}chet Distance}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.28},
  URN =		{urn:nbn:de:0030-drops-169660},
  doi =		{10.4230/LIPIcs.ESA.2022.28},
  annote =	{Keywords: Clustering, Set cover, Fr\'{e}chet distance, Approximation algorithms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.46
On Computing the k-Shortcut Fréchet Distance

Authors: Jacobus Conradi and Anne Driemel

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The Fréchet distance is a popular measure of dissimilarity for polygonal curves. It is defined as a min-max formulation that considers all direction-preserving continuous bijections of the two curves. Because of its susceptibility to noise, Driemel and Har-Peled introduced the shortcut Fréchet distance in 2012, where one is allowed to take shortcuts along one of the curves, similar to the edit distance for sequences. We analyse the parameterized version of this problem, where the number of shortcuts is bounded by a parameter k. The corresponding decision problem can be stated as follows: Given two polygonal curves T and B of at most n vertices, a parameter k and a distance threshold δ, is it possible to introduce k shortcuts along B such that the Fréchet distance of the resulting curve and the curve T is at most δ? We study this problem for polygonal curves in the plane. We provide a complexity analysis for this problem with the following results: (i) assuming the exponential-time-hypothesis (ETH), there exists no algorithm with running time bounded by n^o(k); (ii) there exists a decision algorithm with running time in O(k n^{2k+2} log n). In contrast, we also show that efficient approximate decider algorithms are possible, even when k is large. We present a (3+ε)-approximate decider algorithm with running time in O(k n² log² n) for fixed ε. In addition, we can show that, if k is a constant and the two curves are c-packed for some constant c, then the approximate decider algorithm runs in near-linear time.
Cite as

Jacobus Conradi and Anne Driemel. On Computing the k-Shortcut Fréchet Distance. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.ICALP.2022.46,
  author =	{Conradi, Jacobus and Driemel, Anne},
  title =	{{On Computing the k-Shortcut Fr\'{e}chet Distance}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.46},
  URN =		{urn:nbn:de:0030-drops-163875},
  doi =		{10.4230/LIPIcs.ICALP.2022.46},
  annote =	{Keywords: Fr\'{e}chet distance, Partial similarity, Conditional lower bounds, Approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.7
Minimum-Error Triangulations for Sea Surface Reconstruction

Authors: Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
We apply state-of-the-art computational geometry methods to the problem of reconstructing a time-varying sea surface from tide gauge records. Our work builds on a recent article by Nitzke et al. (Computers & Geosciences, 157:104920, 2021) who have suggested to learn a triangulation D of a given set of tide gauge stations. The objective is to minimize the misfit of the piecewise linear surface induced by D to a reference surface that has been acquired with satellite altimetry. The authors restricted their search to k-order Delaunay (k-OD) triangulations and used an integer linear program in order to solve the resulting optimization problem. In geometric terms, the input to our problem consists of two sets of points in ℝ² with elevations: a set 𝒮 that is to be triangulated, and a set ℛ of reference points. Intuitively, we define the error of a triangulation as the average vertical distance of a point in ℛ to the triangulated surface that is obtained by interpolating elevations of 𝒮 linearly in each triangle. Our goal is to find the triangulation of 𝒮 that has minimum error with respect to ℛ. In our work, we prove that the minimum-error triangulation problem is NP-hard and cannot be approximated within any multiplicative factor in polynomial time unless P = NP. At the same time we show that the problem instances that occur in our application (considering sea level data from several hundreds of tide gauge stations worldwide) can be solved relatively fast using dynamic programming when restricted to k-OD triangulations for k ≤ 7. In particular, instances for which the number of connected components of the so-called k-OD fixed-edge graph is small can be solved within few seconds.
Cite as

Anna Arutyunova, Anne Driemel, Jan-Henrik Haunert, Herman Haverkort, Jürgen Kusche, Elmar Langetepe, Philip Mayer, Petra Mutzel, and Heiko Röglin. Minimum-Error Triangulations for Sea Surface Reconstruction. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 7:1-7:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{arutyunova_et_al:LIPIcs.SoCG.2022.7,
  author =	{Arutyunova, Anna and Driemel, Anne and Haunert, Jan-Henrik and Haverkort, Herman and Kusche, J\"{u}rgen and Langetepe, Elmar and Mayer, Philip and Mutzel, Petra and R\"{o}glin, Heiko},
  title =	{{Minimum-Error Triangulations for Sea Surface Reconstruction}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{7:1--7:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.7},
  URN =		{urn:nbn:de:0030-drops-160155},
  doi =		{10.4230/LIPIcs.SoCG.2022.7},
  annote =	{Keywords: Minimum-Error Triangulation, k-Order Delaunay Triangulations, Data dependent Triangulations, Sea Surface Reconstruction, fixed-Edge Graph}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.36
On the Discrete Fréchet Distance in a Graph

Authors: Anne Driemel, Ivor van der Hoog, and Eva Rotenberg

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
The Fréchet distance is a well-studied similarity measure between curves that is widely used throughout computer science. Motivated by applications where curves stem from paths and walks on an underlying graph (such as a road network), we define and study the Fréchet distance for paths and walks on graphs. When provided with a distance oracle of G with O(1) query time, the classical quadratic-time dynamic program can compute the Fréchet distance between two walks P and Q in a graph G in O(|P|⋅|Q|) time. We show that there are situations where the graph structure helps with computing Fréchet distance: when the graph G is planar, we apply existing (approximate) distance oracles to compute a (1+ε)-approximation of the Fréchet distance between any shortest path P and any walk Q in O(|G|log|G|/√ε+|P|+|Q|/ε) time. We generalise this result to near-shortest paths, i.e. κ-straight paths, as we show how to compute a (1+ε)-approximation between a κ-straight path P and any walk Q in O(|G|log|G|/√ε+|P|+(κ|Q|)/ε) time. Our algorithmic results hold for both the strong and the weak discrete Fréchet distance over the shortest path metric in G. Finally, we show that additional assumptions on the input, such as our assumption on path straightness, are indeed necessary to obtain truly subquadratic running time. We provide a conditional lower bound showing that the Fréchet distance, or even its 1.01-approximation, between arbitrary paths in a weighted planar graph cannot be computed in O((|P|⋅|Q|)^{1-δ}) time for any δ > 0 unless the Orthogonal Vector Hypothesis fails. For walks, this lower bound holds even when G is planar, unit-weight and has O(1) vertices.
Cite as

Anne Driemel, Ivor van der Hoog, and Eva Rotenberg. On the Discrete Fréchet Distance in a Graph. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{driemel_et_al:LIPIcs.SoCG.2022.36,
  author =	{Driemel, Anne and van der Hoog, Ivor and Rotenberg, Eva},
  title =	{{On the Discrete Fr\'{e}chet Distance in a Graph}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.36},
  URN =		{urn:nbn:de:0030-drops-160448},
  doi =		{10.4230/LIPIcs.SoCG.2022.36},
  annote =	{Keywords: Fr\'{e}chet, graphs, planar, complexity analysis}
}
Document
DOI: 10.4230/DagRep.11.4.1
Computational Geometry (Dagstuhl Seminar 21181)

Authors: Siu-Wing Cheng, Anne Driemel, and Jeff M. Phillips

Published in: Dagstuhl Reports, Volume 11, Issue 4 (2021)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 21181 "Computational Geometry". The seminar was held from May 2 to May 7, 2021. Because of COVID, the seminar was held online in a virtual manner, and 36 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.
Cite as

Siu-Wing Cheng, Anne Driemel, and Jeff M. Phillips. Computational Geometry (Dagstuhl Seminar 21181). In Dagstuhl Reports, Volume 11, Issue 4, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.11.4.1,
  author =	{Cheng, Siu-Wing and Driemel, Anne and Phillips, Jeff M.},
  title =	{{Computational Geometry (Dagstuhl Seminar 21181)}},
  pages =	{1--19},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{4},
  editor =	{Cheng, Siu-Wing and Driemel, Anne and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.4.1},
  URN =		{urn:nbn:de:0030-drops-147963},
  doi =		{10.4230/DagRep.11.4.1},
  annote =	{Keywords: algorithms, computational geometry, Computational topology, data structures, Discrete geometry}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.II.6
Bicriteria Aggregation of Polygons via Graph Cuts

Authors: Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, and Jan-Henrik Haunert

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

Abstract
We present a new method for the task of detecting groups of polygons in a given geographic data set and computing a representative polygon for each group. This task is relevant in map generalization where the aim is to derive a less detailed map from a given map. Following a classical approach, we define the output polygons by merging the input polygons with a set of triangles that we select from a constrained Delaunay triangulation of the input polygons' exterior. The innovation of our method is to compute the selection of triangles by solving a bicriteria optimization problem. While on the one hand we aim at minimizing the total area of the outputs polygons, we aim on the other hand at minimizing their total perimeter. We combine these two objectives in a weighted sum and study two computational problems that naturally arise. In the first problem, the parameter that balances the two objectives is fixed and the aim is to compute a single optimal solution. In the second problem, the aim is to compute a set containing an optimal solution for every possible value of the parameter. We present efficient algorithms for these problems based on computing a minimum cut in an appropriately defined graph. Moreover, we show how the result set of the second problem can be approximated with few solutions. In an experimental evaluation, we finally show that the method is able to derive settlement areas from building footprints that are similar to reference solutions.
Cite as

Peter Rottmann, Anne Driemel, Herman Haverkort, Heiko Röglin, and Jan-Henrik Haunert. Bicriteria Aggregation of Polygons via Graph Cuts. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part II. Leibniz International Proceedings in Informatics (LIPIcs), Volume 208, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{rottmann_et_al:LIPIcs.GIScience.2021.II.6,
  author =	{Rottmann, Peter and Driemel, Anne and Haverkort, Herman and R\"{o}glin, Heiko and Haunert, Jan-Henrik},
  title =	{{Bicriteria Aggregation of Polygons via Graph Cuts}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part II},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-208-2},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{208},
  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.II.6},
  URN =		{urn:nbn:de:0030-drops-147658},
  doi =		{10.4230/LIPIcs.GIScience.2021.II.6},
  annote =	{Keywords: map generalization, aggregation, graph cuts, bicriteria optimization}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2020.19
On the Hardness of Computing an Average Curve

Authors: Kevin Buchin, Anne Driemel, and Martijn Struijs

Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)

Abstract
We 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. Building upon recent hardness results for the minimum-enclosing-ball problem under the Fréchet distance, we show that also the 1-median problem is NP-hard. 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. This yields an independent proof of an earlier result by Bulteau et al. from 2018 for a variant of DTW that uses squared distances, where the new proof is both simpler and more general. On the positive side, we give approximation algorithms for problem variants 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.
Cite as

Kevin Buchin, Anne Driemel, and Martijn Struijs. On the Hardness of Computing an Average Curve. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 19:1-19:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SWAT.2020.19,
  author =	{Buchin, Kevin and Driemel, Anne and Struijs, Martijn},
  title =	{{On the Hardness of Computing an Average Curve}},
  booktitle =	{17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)},
  pages =	{19:1--19:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-150-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{162},
  editor =	{Albers, Susanne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.19},
  URN =		{urn:nbn:de:0030-drops-122662},
  doi =		{10.4230/LIPIcs.SWAT.2020.19},
  annote =	{Keywords: Curves, Clustering, Algorithms, Hardness, Approximation}
}
Document
DOI: 10.4230/DagRep.9.4.107
Computational Geometry (Dagstuhl Seminar 19181)

Authors: Siu-Wing Cheng, Anne Driemel, and Jeff Erickson

Published in: Dagstuhl Reports, Volume 9, Issue 4 (2019)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 19181 "Computational Geometry". The seminar was held from April 28 to May 3, 2019 and 40 participants from various countries attended it. New advances and directions in computational geometry were presented and discussed. The report collects the abstracts of talks and open problems presented in the seminar.
Cite as

Siu-Wing Cheng, Anne Driemel, and Jeff Erickson. Computational Geometry (Dagstuhl Seminar 19181). In Dagstuhl Reports, Volume 9, Issue 4, pp. 107-123, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{cheng_et_al:DagRep.9.4.107,
  author =	{Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff},
  title =	{{Computational Geometry (Dagstuhl Seminar 19181)}},
  pages =	{107--123},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{4},
  editor =	{Cheng, Siu-Wing and Driemel, Anne and Erickson, Jeff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.4.107},
  URN =		{urn:nbn:de:0030-drops-113064},
  doi =		{10.4230/DagRep.9.4.107},
  annote =	{Keywords: Computational geometry, polynomial partition, geometric data structures, approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.28
The VC Dimension of Metric Balls Under Fréchet and Hausdorff Distances

Authors: Anne Driemel, Jeff M. Phillips, and Ioannis Psarros

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract
The Vapnik-Chervonenkis dimension provides a notion of complexity for systems of sets. If the VC dimension is small, then knowing this can drastically simplify fundamental computational tasks such as classification, range counting, and density estimation through the use of sampling bounds. We analyze set systems where the ground set X is a set of polygonal curves in R^d and the sets {R} are metric balls defined by curve similarity metrics, such as the Fréchet distance and the Hausdorff distance, as well as their discrete counterparts. We derive upper and lower bounds on the VC dimension that imply useful sampling bounds in the setting that the number of curves is large, but the complexity of the individual curves is small. Our upper bounds are either near-quadratic or near-linear in the complexity of the curves that define the ranges and they are logarithmic in the complexity of the curves that define the ground set.
Cite as

Anne Driemel, Jeff M. Phillips, and Ioannis Psarros. The VC Dimension of Metric Balls Under Fréchet and Hausdorff Distances. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{driemel_et_al:LIPIcs.SoCG.2019.28,
  author =	{Driemel, Anne and Phillips, Jeff M. and Psarros, Ioannis},
  title =	{{The VC Dimension of Metric Balls Under Fr\'{e}chet and Hausdorff Distances}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.28},
  URN =		{urn:nbn:de:0030-drops-104329},
  doi =		{10.4230/LIPIcs.SoCG.2019.28},
  annote =	{Keywords: VC dimension, Fr\'{e}chet distance, Hausdorff distance}
}
Document
DOI: 10.4230/DagRep.7.4.107
Computational Geometry (Dagstuhl Seminar 17171)

Authors: Orfried Cheong, Anne Driemel, and Jeff Erickson

Published in: Dagstuhl Reports, Volume 7, Issue 4 (2018)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17171 "Computational Geometry". The seminar was held from 23rd to 28th April 2017 and 47 participants from various countries attended it. Recent advances in computational geometry were presented and new challenges were identified. The report collects the abstracts of talks and open problems presented in the seminar.
Cite as

Orfried Cheong, Anne Driemel, and Jeff Erickson. Computational Geometry (Dagstuhl Seminar 17171). In Dagstuhl Reports, Volume 7, Issue 4, pp. 107-127, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{cheong_et_al:DagRep.7.4.107,
  author =	{Cheong, Orfried and Driemel, Anne and Erickson, Jeff},
  title =	{{Computational Geometry (Dagstuhl Seminar 17171)}},
  pages =	{107--127},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{4},
  editor =	{Cheong, Orfried and Driemel, Anne and Erickson, Jeff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.4.107},
  URN =		{urn:nbn:de:0030-drops-82771},
  doi =		{10.4230/DagRep.7.4.107},
  annote =	{Keywords: algorithms, applications, combinatorics, complexity, geometric computing, high-dimensional computational geometry, implementation, monitoring and shape data}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.37
Locality-Sensitive Hashing of Curves

Authors: Anne Driemel and Francesco Silvestri

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
We study data structures for storing a set of polygonal curves in R^d such that, given a query curve, we can efficiently retrieve similar curves from the set, where similarity is measured using the discrete Fréchet distance or the dynamic time warping distance. To this end we devise the first locality-sensitive hashing schemes for these distance measures. A major challenge is posed by the fact that these distance measures internally optimize the alignment between the curves. We give solutions for different types of alignments including constrained and unconstrained versions. For unconstrained alignments, we improve over a result by Indyk [SoCG 2002] for short curves. Let n be the number of input curves and let m be the maximum complexity of a curve in the input. In the particular case where m <= (a/(4d)) log n, for some fixed a>0, our solutions imply an approximate near-neighbor data structure for the discrete Fréchet distance that uses space in O(n^(1+a) log n) and achieves query time in O(n^a log^2 n) and constant approximation factor. Furthermore, our solutions provide a trade-off between approximation quality and computational performance: for any parameter k in [m], we can give a data structure that uses space in O(2^(2k) m^(k-1) n log n + nm), answers queries in O( 2^(2k) m^(k) log n) time and achieves approximation factor in O(m/k).
Cite as

Anne Driemel and Francesco Silvestri. Locality-Sensitive Hashing of Curves. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 37:1-37:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{driemel_et_al:LIPIcs.SoCG.2017.37,
  author =	{Driemel, Anne and Silvestri, Francesco},
  title =	{{Locality-Sensitive Hashing of Curves}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.37},
  URN =		{urn:nbn:de:0030-drops-72032},
  doi =		{10.4230/LIPIcs.SoCG.2017.37},
  annote =	{Keywords: Locality-Sensitive Hashing, Frechet distance, Dynamic Time Warping}
}
Document
DOI: 10.4230/DagSemProc.10491.3
10491 Results of the break-out group: Aggregation

Authors: Mark de Berg, Jörg-Rüdiger Sack, Bettina Speckmann, Anne Driemel, Maike Buchin, Monika Sester, and Marc van Kreveld

Published in: Dagstuhl Seminar Proceedings, Volume 10491, Representation, Analysis and Visualization of Moving Objects (2011)

Abstract
We discussed different problems that arise when aggregating trajectories: how to segment the input, whether to use original parts of the input trajectories, as opposed to an ``averaged'' path and how to simplify the aggregated structure. We give examples where these questions are not easily answered.
Cite as

Mark de Berg, Jörg-Rüdiger Sack, Bettina Speckmann, Anne Driemel, Maike Buchin, Monika Sester, and Marc van Kreveld. 10491 Results of the break-out group: Aggregation. In Representation, Analysis and Visualization of Moving Objects. Dagstuhl Seminar Proceedings, Volume 10491, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:DagSemProc.10491.3,
  author =	{de Berg, Mark and Sack, J\"{o}rg-R\"{u}diger and Speckmann, Bettina and Driemel, Anne and Buchin, Maike and Sester, Monika and van Kreveld, Marc},
  title =	{{10491 Results of the break-out group: Aggregation}},
  booktitle =	{Representation, Analysis and Visualization of Moving Objects},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2011},
  volume =	{10491},
  editor =	{J\"{o}rg-R\"{u}diger Sack and Bettina Speckmann and Emiel Van Loon and Robert Weibel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.10491.3},
  URN =		{urn:nbn:de:0030-drops-29878},
  doi =		{10.4230/DagSemProc.10491.3},
  annote =	{Keywords: Aggregation, Trajectories, Generalization, Map Generation}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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