Search Results

Documents authored by Ophelders, Tim

Document
DOI: 10.4230/LIPIcs.SoCG.2024.63
Faster Fréchet Distance Approximation Through Truncated Smoothing

Authors: Thijs van der Horst and Tim Ophelders

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The Fréchet distance is a popular distance measure for curves. Computing the Fréchet distance between two polygonal curves of n vertices takes roughly quadratic time, and conditional lower bounds suggest that even approximating to within a factor 3 cannot be done in strongly-subquadratic time, even in one dimension. The current best approximation algorithms present trade-offs between approximation quality and running time. Recently, van der Horst et al. (SODA, 2023) presented an O((n²/α) log³ n) time α-approximate algorithm for curves in arbitrary dimensions, for any α ∈ [1, n]. Our main contribution is an approximation algorithm for curves in one dimension, with a significantly faster running time of O(n log³ n + (n²/α³) log²n log log n). Additionally, we give an algorithm for curves in arbitrary dimensions that improves upon the state-of-the-art running time by a logarithmic factor, to O((n²/α) log² n). Both of our algorithms rely on a linear-time simplification procedure that in one dimension reduces the complexity of the reachable free space to O(n²/α) without making sacrifices in the asymptotic approximation factor.
Cite as

Thijs van der Horst and Tim Ophelders. Faster Fréchet Distance Approximation Through Truncated Smoothing. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanderhorst_et_al:LIPIcs.SoCG.2024.63,
  author =	{van der Horst, Thijs and Ophelders, Tim},
  title =	{{Faster Fr\'{e}chet Distance Approximation Through Truncated Smoothing}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang 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/LIPIcs.SoCG.2024.63},
  URN =		{urn:nbn:de:0030-drops-200083},
  doi =		{10.4230/LIPIcs.SoCG.2024.63},
  annote =	{Keywords: Fr\'{e}cht distance, approximation algorithms, simplification}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2024.89
Optimal In-Place Compaction of Sliding Cubes (Media Exposition)

Authors: Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. This note accompanies a video that explains our in-place algorithm for reconfiguration in the sliding cubes model. Specifically, our algorithm [Irina Kostitsyna et al., 2023] reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. As is common in the literature, we can then reconfigure between two arbitrary shapes via their canonical configurations. The number of moves performed by our algorithm is asymptotically worst-case optimal and strictly improves upon the current state-of-the-art.
Cite as

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal In-Place Compaction of Sliding Cubes (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 89:1-89:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SoCG.2024.89,
  author =	{Kostitsyna, Irina and Ophelders, Tim and Parada, Irene and Peters, Tom and Sonke, Willem and Speckmann, Bettina},
  title =	{{Optimal In-Place Compaction of Sliding Cubes}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{89:1--89:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang 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/LIPIcs.SoCG.2024.89},
  URN =		{urn:nbn:de:0030-drops-200347},
  doi =		{10.4230/LIPIcs.SoCG.2024.89},
  annote =	{Keywords: Sliding cubes, Reconfiguration algorithm, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.31
Optimal In-Place Compaction of Sliding Cubes

Authors: Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann

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

Abstract
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. As is common in the literature, we focus on reconfiguration via an intermediate canonical shape. Specifically, we present an in-place algorithm that reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. This result is asymptotically optimal and strictly improves on all prior work. Furthermore, our algorithm directly extends to dimensions higher than three.
Cite as

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal In-Place Compaction of Sliding Cubes. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SWAT.2024.31,
  author =	{Kostitsyna, Irina and Ophelders, Tim and Parada, Irene and Peters, Tom and Sonke, Willem and Speckmann, Bettina},
  title =	{{Optimal In-Place Compaction of Sliding Cubes}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{31:1--31:14},
  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.31},
  URN =		{urn:nbn:de:0030-drops-200713},
  doi =		{10.4230/LIPIcs.SWAT.2024.31},
  annote =	{Keywords: Sliding cubes, Reconfiguration algorithm, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.48
Shortest Paths in Portalgons

Authors: Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
Any surface that is intrinsically polyhedral can be represented by a collection of simple polygons (fragments), glued along pairs of equally long oriented edges, where each fragment is endowed with the geodesic metric arising from its Euclidean metric. We refer to such a representation as a portalgon, and we call two portalgons equivalent if the surfaces they represent are isometric. We analyze the complexity of shortest paths. We call a fragment happy if any shortest path on the portalgon visits it at most a constant number of times. A portalgon is happy if all of its fragments are happy. We present an efficient algorithm to compute shortest paths on happy portalgons. The number of times that a shortest path visits a fragment is unbounded in general. We contrast this by showing that the intrinsic Delaunay triangulation of any polyhedral surface corresponds to a happy portalgon. Since computing the intrinsic Delaunay triangulation may be inefficient, we provide an efficient algorithm to compute happy portalgons for a restricted class of portalgons.
Cite as

Maarten Löffler, Tim Ophelders, Rodrigo I. Silveira, and Frank Staals. Shortest Paths in Portalgons. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.SoCG.2023.48,
  author =	{L\"{o}ffler, Maarten and Ophelders, Tim and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Shortest Paths in Portalgons}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{48:1--48:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.48},
  URN =		{urn:nbn:de:0030-drops-178980},
  doi =		{10.4230/LIPIcs.SoCG.2023.48},
  annote =	{Keywords: Polyhedral surfaces, shortest paths, geodesic distance, Delaunay triangulation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.29
Efficient Fréchet Distance Queries for Segments

Authors: Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals

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

Abstract
We study the problem of constructing a data structure that can store a two-dimensional polygonal curve P, such that for any query segment ab one can efficiently compute the Fréchet distance between P and ab. First we present a data structure of size O(n log n) that can compute the Fréchet distance between P and a horizontal query segment ab in O(log n) time, where n is the number of vertices of P. In comparison to prior work, this significantly reduces the required space. We extend the type of queries allowed, as we allow a query to be a horizontal segment ab together with two points s, t ∈ P (not necessarily vertices), and ask for the Fréchet distance between ab and the curve of P in between s and t. Using O(nlog²n) storage, such queries take O(log³ n) time, simplifying and significantly improving previous results. We then generalize our results to query segments of arbitrary orientation. We present an O(nk^{3+ε}+n²) size data structure, where k ∈ [1,n] is a parameter the user can choose, and ε > 0 is an arbitrarily small constant, such that given any segment ab and two points s, t ∈ P we can compute the Fréchet distance between ab and the curve of P in between s and t in O((n/k)log²n+log⁴ n) time. This is the first result that allows efficient exact Fréchet distance queries for arbitrarily oriented segments. We also present two applications of our data structure. First, we show that our data structure allows us to compute a local δ-simplification (with respect to the Fréchet distance) of a polygonal curve in O(n^{5/2+ε}) time, improving a previous O(n³) time algorithm. Second, we show that we can efficiently find a translation of an arbitrary query segment ab that minimizes the Fréchet distance with respect to a subcurve of P.
Cite as

Maike Buchin, Ivor van der Hoog, Tim Ophelders, Lena Schlipf, Rodrigo I. Silveira, and Frank Staals. Efficient Fréchet Distance Queries for Segments. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 29:1-29:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.ESA.2022.29,
  author =	{Buchin, Maike and van der Hoog, Ivor and Ophelders, Tim and Schlipf, Lena and Silveira, Rodrigo I. and Staals, Frank},
  title =	{{Efficient Fr\'{e}chet Distance Queries for Segments}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{29:1--29:14},
  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.29},
  URN =		{urn:nbn:de:0030-drops-169671},
  doi =		{10.4230/LIPIcs.ESA.2022.29},
  annote =	{Keywords: Computational Geometry, Data Structures, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.55
Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals

Authors: Tim Ophelders and Salman Parsa

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

Abstract
We consider drawings of graphs in the plane in which vertices are assigned distinct points in the plane and edges are drawn as simple curves connecting the vertices and such that the edges intersect only at their common endpoints. There is an intuitive quality measure for drawings of a graph that measures the height of a drawing ϕ : G↪ℝ² as follows. For a vertical line 𝓁 in ℝ², let the height of 𝓁 be the cardinality of the set 𝓁 ∩ ϕ(G). The height of a drawing of G is the maximum height over all vertical lines. In this paper, instead of abstract graphs, we fix a drawing and consider plane graphs. In other words, we are looking for a homeomorphism of the plane that minimizes the height of the resulting drawing. This problem is equivalent to the homotopy height problem in the plane, and the homotopic Fréchet distance problem. These problems were recently shown to lie in NP, but no polynomial-time algorithm or NP-hardness proof has been found since their formulation in 2009. We present the first polynomial-time algorithm for drawing trees with optimal height. This corresponds to a polynomial-time algorithm for the homotopy height where the triangulation has only one vertex (that is, a set of loops incident to a single vertex), so that its dual is a tree.
Cite as

Tim Ophelders and Salman Parsa. Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{ophelders_et_al:LIPIcs.SoCG.2022.55,
  author =	{Ophelders, Tim and Parsa, Salman},
  title =	{{Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{55:1--55:16},
  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.55},
  URN =		{urn:nbn:de:0030-drops-160631},
  doi =		{10.4230/LIPIcs.SoCG.2022.55},
  annote =	{Keywords: Graph drawing, homotopy height}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.22
A Family of Metrics from the Truncated Smoothing of Reeb Graphs

Authors: Erin Wolf Chambers, Elizabeth Munch, and Tim Ophelders

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
In this paper, we introduce an extension of smoothing on Reeb graphs, which we call truncated smoothing; this in turn allows us to define a new family of metrics which generalize the interleaving distance for Reeb graphs. Intuitively, we "chop off" parts near local minima and maxima during the course of smoothing, where the amount cut is controlled by a parameter τ. After formalizing truncation as a functor, we show that when applied after the smoothing functor, this prevents extensive expansion of the range of the function, and yields particularly nice properties (such as maintaining connectivity) when combined with smoothing for 0 ≤ τ ≤ 2ε, where ε is the smoothing parameter. Then, for the restriction of τ ∈ [0,ε], we have additional structure which we can take advantage of to construct a categorical flow for any choice of slope m ∈ [0,1]. Using the infrastructure built for a category with a flow, this then gives an interleaving distance for every m ∈ [0,1], which is a generalization of the original interleaving distance, which is the case m = 0. While the resulting metrics are not stable, we show that any pair of these for m, m' ∈ [0,1) are strongly equivalent metrics, which in turn gives stability of each metric up to a multiplicative constant. We conclude by discussing implications of this metric within the broader family of metrics for Reeb graphs.
Cite as

Erin Wolf Chambers, Elizabeth Munch, and Tim Ophelders. A Family of Metrics from the Truncated Smoothing of Reeb Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2021.22,
  author =	{Chambers, Erin Wolf and Munch, Elizabeth and Ophelders, Tim},
  title =	{{A Family of Metrics from the Truncated Smoothing of Reeb Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.22},
  URN =		{urn:nbn:de:0030-drops-138218},
  doi =		{10.4230/LIPIcs.SoCG.2021.22},
  annote =	{Keywords: Reeb graphs, interleaving distance, graphical signatures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.55
Polygon-Universal Graphs

Authors: Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study a fundamental question from graph drawing: given a pair (G,C) of a graph G and a cycle C in G together with a simple polygon P, is there a straight-line drawing of G inside P which maps C to P? We say that such a drawing of (G,C) respects P. We fully characterize those instances (G,C) which are polygon-universal, that is, they have a drawing that respects P for any simple (not necessarily convex) polygon P. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance (G,C) is planar, that is, if there exists a planar drawing of G with C on the outer face, we show that the same conditions guarantee for every simple polygon P the existence of a planar drawing of (G,C) that respects P. If (G,C) is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon P.
Cite as

Tim Ophelders, Ignaz Rutter, Bettina Speckmann, and Kevin Verbeek. Polygon-Universal Graphs. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ophelders_et_al:LIPIcs.SoCG.2021.55,
  author =	{Ophelders, Tim and Rutter, Ignaz and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Polygon-Universal Graphs}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{55:1--55:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.55},
  URN =		{urn:nbn:de:0030-drops-138540},
  doi =		{10.4230/LIPIcs.SoCG.2021.55},
  annote =	{Keywords: Graph drawing, partial drawing extension, simple polygon}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.13
Between Shapes, Using the Hausdorff Distance

Authors: Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
Given two shapes A and B in the plane with Hausdorff distance 1, is there a shape S with Hausdorff distance 1/2 to and from A and B? The answer is always yes, and depending on convexity of A and/or B, S may be convex, connected, or disconnected. We show a generalization of this result on Hausdorff distances and middle shapes, and show some related properties. We also show that a generalization of such middle shapes implies a morph with a bounded rate of change. Finally, we explore a generalization of the concept of a Hausdorff middle to more than two sets and show how to approximate or compute it.
Cite as

Marc van Kreveld, Tillmann Miltzow, Tim Ophelders, Willem Sonke, and Jordi L. Vermeulen. Between Shapes, Using the Hausdorff Distance. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.ISAAC.2020.13,
  author =	{van Kreveld, Marc and Miltzow, Tillmann and Ophelders, Tim and Sonke, Willem and Vermeulen, Jordi L.},
  title =	{{Between Shapes, Using the Hausdorff Distance}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.13},
  URN =		{urn:nbn:de:0030-drops-133572},
  doi =		{10.4230/LIPIcs.ISAAC.2020.13},
  annote =	{Keywords: computational geometry, Hausdorff distance, shape interpolation}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2021.I.16
Volume from Outlines on Terrains

Authors: Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek

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

Abstract
Outlines (closed loops) delineate areas of interest on terrains, such as regions with a heightened risk of landslides. For various analysis tasks it is necessary to define and compute a volume of earth (soil) based on such an outline, capturing, for example, the possible volume of a landslide in a high-risk region. In this paper we discuss several options to define meaningful 2D surfaces induced by a 1D outline, which allow us to compute such volumes. We experimentally compare the proposed surface options for two applications: similarity of paths on terrains and landslide susceptibility analysis.
Cite as

Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Volume from Outlines on Terrains. In 11th International Conference on Geographic Information Science (GIScience 2021) - Part I. Leibniz International Proceedings in Informatics (LIPIcs), Volume 177, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{vankreveld_et_al:LIPIcs.GIScience.2021.I.16,
  author =	{van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Volume from Outlines on Terrains}},
  booktitle =	{11th International Conference on Geographic Information Science (GIScience 2021) - Part I},
  pages =	{16:1--16:15},
  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.16},
  URN =		{urn:nbn:de:0030-drops-130512},
  doi =		{10.4230/LIPIcs.GIScience.2021.I.16},
  annote =	{Keywords: Terrain model, similarity, volume, computation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2019.22
Convex Polygons in Cartesian Products

Authors: Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot

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

Abstract
We study several problems concerning convex polygons whose vertices lie in a Cartesian product of two sets of n real numbers (for short, grid). First, we prove that every such grid contains a convex polygon with Omega(log n) vertices and that this bound is tight up to a constant factor. We generalize this result to d dimensions (for a fixed d in N), and obtain a tight lower bound of Omega(log^{d-1}n) for the maximum number of points in convex position in a d-dimensional grid. Second, we present polynomial-time algorithms for computing the longest convex polygonal chain in a grid that contains no two points with the same x- or y-coordinate. We show that the maximum size of such a convex polygon can be efficiently approximated up to a factor of 2. Finally, we present exponential bounds on the maximum number of convex polygons in these grids, and for some restricted variants. These bounds are tight up to polynomial factors.
Cite as

Jean-Lou De Carufel, Adrian Dumitrescu, Wouter Meulemans, Tim Ophelders, Claire Pennarun, Csaba D. Tóth, and Sander Verdonschot. Convex Polygons in Cartesian Products. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{decarufel_et_al:LIPIcs.SoCG.2019.22,
  author =	{De Carufel, Jean-Lou and Dumitrescu, Adrian and Meulemans, Wouter and Ophelders, Tim and Pennarun, Claire and T\'{o}th, Csaba D. and Verdonschot, Sander},
  title =	{{Convex Polygons in Cartesian Products}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{22:1--22:17},
  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.22},
  URN =		{urn:nbn:de:0030-drops-104267},
  doi =		{10.4230/LIPIcs.SoCG.2019.22},
  annote =	{Keywords: Erd\H{o}s-Szekeres theorem, Cartesian product, convexity, polyhedron, recursive construction, approximation algorithm}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.23
Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary

Authors: Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.
Cite as

Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann. Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{burton_et_al:LIPIcs.ESA.2017.23,
  author =	{Burton, Benjamin and Chambers, Erin and van Kreveld, Marc and Meulemans, Wouter and Ophelders, Tim and Speckmann, Bettina},
  title =	{{Computing Optimal Homotopies over a Spiked Plane with Polygonal Boundary}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{23:1--23:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.23},
  URN =		{urn:nbn:de:0030-drops-78630},
  doi =		{10.4230/LIPIcs.ESA.2017.23},
  annote =	{Keywords: Fr\'{e}chet distance, polygonal domain, homotopy, geodesic, obstacle}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.48
Computing Representative Networks for Braided Rivers

Authors: Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek

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

Abstract
Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are delta-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum delta-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.
Cite as

Maarten Kleinhans, Marc van Kreveld, Tim Ophelders, Willem Sonke, Bettina Speckmann, and Kevin Verbeek. Computing Representative Networks for Braided Rivers. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kleinhans_et_al:LIPIcs.SoCG.2017.48,
  author =	{Kleinhans, Maarten and van Kreveld, Marc and Ophelders, Tim and Sonke, Willem and Speckmann, Bettina and Verbeek, Kevin},
  title =	{{Computing Representative Networks for Braided Rivers}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{48:1--48: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.48},
  URN =		{urn:nbn:de:0030-drops-72204},
  doi =		{10.4230/LIPIcs.SoCG.2017.48},
  annote =	{Keywords: braided rivers, Morse-Smale complex, persistence, network extraction, polyhedral terrain}
}
Document
DOI: 10.4230/LIPIcs.FUN.2016.11
The Complexity of Snake

Authors: Marzio De Biasi and Tim Ophelders

Published in: LIPIcs, Volume 49, 8th International Conference on Fun with Algorithms (FUN 2016)

Abstract
Snake and Nibbler are two well-known video games in which a snake slithers through a maze and grows as it collects food. During this process, the snake must avoid any collision with its tail. Various goals can be associated with these video games, such as avoiding the tail as long as possible, or collecting a certain amount of food, or reaching some target location. Unfortunately, like many other motion-planning problems, even very restricted variants are computationally intractable. In particular, we prove the NP--hardness of collecting all food on solid grid graphs; as well as its PSPACE-completeness on general grid graphs. Moreover, given an initial and a target configuration of the snake, moving from one configuration to the other is PSPACE-complete, even on grid graphs without food, or with an initially short snake. Our results make use of the nondeterministic constraint logic framework by Hearn and Demaine, which has been used to analyze the computational complexity of many games and puzzles. We extend this framework for the analysis of puzzles whose initial state is chosen by the player.
Cite as

Marzio De Biasi and Tim Ophelders. The Complexity of Snake. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{debiasi_et_al:LIPIcs.FUN.2016.11,
  author =	{De Biasi, Marzio and Ophelders, Tim},
  title =	{{The Complexity of Snake}},
  booktitle =	{8th International Conference on Fun with Algorithms (FUN 2016)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-005-7},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{49},
  editor =	{Demaine, Erik D. and Grandoni, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2016.11},
  URN =		{urn:nbn:de:0030-drops-58841},
  doi =		{10.4230/LIPIcs.FUN.2016.11},
  annote =	{Keywords: Games, Puzzles, Motion Planning, Nondeterministic Constraint Logic, PSPACE}
}
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