70 Search Results for "Löffler, Maarten"

Document
DOI: 10.4230/LIPIcs.SEA.2026.1
Global Polyline Simplification Under the Fréchet Distance: Theory and Practice

Authors: Christian Abdullahad and Sabine Storandt

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract
Given an input polyline with n vertices, the global polyline simplification problem seeks a simplified polyline with the minimum number of vertices whose distance to the original polyline does not exceed a given bound. For the vertex-restricted variant, where the simplified polyline is required to be a subsequence of the input vertices, an algorithm with a running time of 𝒪(n³) was presented in previous work, using the Fréchet distance as the polyline similarity measure. A closely related variant is the local polyline simplification problem, in which the distance bound is required to hold for every individual shortcut segment replacing a sub-polyline. This condition implies that any locally valid simplification is also globally valid, whereas the converse does not hold. As a consequence, globally optimal simplifications may use substantially fewer vertices than locally optimal ones. Indeed, in previous work, instances were constructed in which the optimal global simplification is smaller by a constant factor. On the algorithmic side, optimal local simplifications can be computed significantly faster, namely in 𝒪(n² log n) under the Fréchet distance, and efficient heuristics are also available. This raises the question of which problem variant is more suitable for practical application. In this paper, we first show that there exist instances for which the optimal solution sizes of global and local polyline simplification differ by a factor in Θ(n), substantially strengthening the previously known constant-factor separation. We then present the first practical implementations of existing algorithms for global polyline simplification and experimentally evaluate their performance. To this end, we introduce several engineering techniques that considerably accelerate these algorithms. Moreover, we develop an implicit Fréchet framework that allows many Fréchet-related problems to be addressed in a weaker computational model. Within this framework, explicit geometric computations can be reduced to simple comparisons, resulting in significantly more robust implementations. Somewhat surprisingly, our experimental results reveal that, despite the large worst-case gap established by our theoretical result, the difference in solution size between optimal global and local simplifications is negligible in practice. Motivated by this observation, we propose a heuristic for global polyline simplification that is guaranteed to produce solutions of size equal to or smaller than the optimal local simplification. On a benchmark consisting of one million polylines, the heuristic yields suboptimal results on only eight while being significantly faster than the optimal algorithms.
Cite as

Christian Abdullahad and Sabine Storandt. Global Polyline Simplification Under the Fréchet Distance: Theory and Practice. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{abdullahad_et_al:LIPIcs.SEA.2026.1,
  author =	{Abdullahad, Christian and Storandt, Sabine},
  title =	{{Global Polyline Simplification Under the Fr\'{e}chet Distance: Theory and Practice}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.1},
  URN =		{urn:nbn:de:0030-drops-260055},
  doi =		{10.4230/LIPIcs.SEA.2026.1},
  annote =	{Keywords: Polyline Simplification, Shortcut Graph, Fr\'{e}chet Distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.17
Fréchet Distance in the Imbalanced Case

Authors: Lotte Blank

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Given two polygonal curves P and Q defined by n and m vertices with m ≤ n, we show that the discrete Fréchet distance in 1D cannot be approximated within a factor of 2-ε in 𝒪((nm)^{1-δ}) time for any ε, δ > 0 unless OVH fails. Using a similar construction, we extend this bound for curves in 2D under the continuous or discrete Fréchet distance and increase the approximation factor to 1+√2-ε (resp. 3-ε) if the curves lie in the Euclidean space (resp. in the L_∞-space). This strengthens the lower bound by Buchin, Ophelders, and Speckmann to the case where m = n^α for α ∈ (0,1) and increases the approximation factor of 1.001 by Bringmann. For the discrete Fréchet distance in 1D, we provide an approximation algorithm with optimal approximation factor and almost optimal running time. Further, for curves in any dimension embedded in any L_p space, we present a (3+ε)-approximation algorithm for the continuous and discrete Fréchet distance using 𝒪((n+m²)log n) time, which almost matches the approximation factor of the lower bound for the L_∞ metric.
Cite as

Lotte Blank. Fréchet Distance in the Imbalanced Case. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blank:LIPIcs.SoCG.2026.17,
  author =	{Blank, Lotte},
  title =	{{Fr\'{e}chet Distance in the Imbalanced Case}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.17},
  URN =		{urn:nbn:de:0030-drops-258232},
  doi =		{10.4230/LIPIcs.SoCG.2026.17},
  annote =	{Keywords: Fr\'{e}chet distance, SETH, Orthogonal Vectors, Lower Bounds, distance oracle, data structures}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.35
On Computing the (Exact) Fréchet Distance with a Frog

Authors: Jacobus Conradi, Ivor van der Hoog, and Eva Rotenberg

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The continuous Fréchet distance 𝒟_F(π,σ) between two polygonal curves π and σ is classically computed by exploring the free space diagram over the two curves. [SoCG'25] recently proposed a radically different approach: they approximate 𝒟_F(π,σ) by computing paths in a discrete graph that models a joint traversal of π and σ, recursively bisecting edges until the discrete distance converges to the continuous one. They implement their "frog-based" technique, and claim that it yields substantial practical speedups compared to the state-of-the-art implementations. In this paper, we revisit this technique. We observe that, in its current form, it has three limitations: (i) it does not use exact arithmetic, (ii) its recursive bisection introduces the required monotonicity events to realise the Fréchet distance only in the limit, and (iii) it applies a heuristic simplification technique which is overly conservative. Motivated by theoretical interest, we develop new techniques that guarantee exactness, polynomial-time convergence and near-optimal lossless simplifications. We provide an open-source C++ implementation of our variant. Our primary contribution is an extensive empirical evaluation on a broad, publically available, suite of real-world and synthetic data sets. Among the frog-based variants, exact computation indeed introduces overhead and increases median runtime. Yet, our new approach is often faster in the worst case, worst ten percent, or even the average runtime due to its worst-case convergence guarantees. More surprisingly, the implementation of [SoCG'19] dominates all frog-based implementations in performance - this finding contrasts previously published claims. These results provide a much-needed nuanced perspective on the capabilities and limitations of frog-based techniques: we showcase its theoretical appeal, but highlight its limited practical feasibility.
Cite as

Jacobus Conradi, Ivor van der Hoog, and Eva Rotenberg. On Computing the (Exact) Fréchet Distance with a Frog. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{conradi_et_al:LIPIcs.SoCG.2026.35,
  author =	{Conradi, Jacobus and van der Hoog, Ivor and Rotenberg, Eva},
  title =	{{On Computing the (Exact) Fr\'{e}chet Distance with a Frog}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.35},
  URN =		{urn:nbn:de:0030-drops-258414},
  doi =		{10.4230/LIPIcs.SoCG.2026.35},
  annote =	{Keywords: Algorithms engineering, Fr\'{e}chet distance}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.40
Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface

Authors: Loïc Dubois

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Every surface that is intrinsically polyhedral can be represented by a portalgon: a collection of polygons in the Euclidean plane with some pairs of equally long edges abstractly identified. While this representation is arguably simpler than meshes (flat polygons in ℝ³ forming a surface), it has unbounded happiness: a shortest path in the surface may visit the same polygon arbitrarily many times. This pathological behavior is an obstacle towards efficient algorithms. On the other hand, Löffler, Ophelders, Staals, and Silveira [SoCG 2023] recently proved that the (intrinsic) Delaunay triangulations have bounded happiness. In this paper, given a closed polyhedral surface S, represented by a triangular portalgon T, we provide an algorithm to compute the Delaunay triangulation of S whose vertices are the singularities of S (the points whose surrounding angle is distinct from 2π). The time complexity of our algorithm is polynomial in the number of triangles and in the logarithm of the aspect ratio r of T. Within our model of computation, we show that the dependency in log r is unavoidable. Our algorithm can be used to pre-process a triangular portalgon before computing shortest paths on its surface, and to determine whether the surfaces of two triangular portalgons are isometric.
Cite as

Loïc Dubois. Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 40:1-40:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{dubois:LIPIcs.SoCG.2026.40,
  author =	{Dubois, Lo\"{i}c},
  title =	{{Computing the Intrinsic Delaunay Triangulation of a Closed Polyhedral Surface}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{40:1--40:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.40},
  URN =		{urn:nbn:de:0030-drops-258460},
  doi =		{10.4230/LIPIcs.SoCG.2026.40},
  annote =	{Keywords: Polyhedral surface, intrinsic Delaunay triangulation, algorithmic complexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.43
Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs

Authors: Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
We study unlabeled multi-robot motion planning for unit-disk robots in a polygonal environment. Although the problem is hard in general, polynomial-time solutions exist under appropriate separation assumptions on start and target positions. Solovey et al. (RSS'15) provide a near-optimal solution assuming that start/target positions must have pairwise distance at least 4, and at least √5≈2.236 from obstacles. This raises the question of whether polynomial-time algorithms can be obtained in even more densely packed environments. In this paper we present a generalized algorithm that achieve different trade-offs on the robots-separation and obstacles-separation bounds, all significantly improving upon the state of the art. Specifically, we obtain polynomial-time constant-approximation algorithms to minimize the total path length when (i) the robots-separation is 2 2/3 and the obstacles-separation is 1 2/3, or (ii) the robots-separation is ≈3.291 and the obstacles-separation ≈1.354. Additionally, we introduce a different strategy yielding a polynomial-time solution when the robots-separation is only 2, and the obstacles-separation is 3. Finally, we show that without any robots-separation assumption, obstacles-separation of at least 1.5 may be necessary for a solution to exist.
Cite as

Tsuri Farhana, Omrit Filtser, and Shalev Goldshtein. Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{farhana_et_al:LIPIcs.SoCG.2026.43,
  author =	{Farhana, Tsuri and Filtser, Omrit and Goldshtein, Shalev},
  title =	{{Unlabeled Multi-Robot Motion Planning with Improved Separation Trade-Offs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{43:1--43:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.43},
  URN =		{urn:nbn:de:0030-drops-258495},
  doi =		{10.4230/LIPIcs.SoCG.2026.43},
  annote =	{Keywords: multi-robot motion planning}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.45
Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications

Authors: Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
The weak visibility polygon of a line segment s inside a simple polygon P, denoted by V_P(s), is the region of the polygon that is visible from at least one point on s. Given its fundamental nature in computational geometry, several algorithms have been proposed to compute weak visibility polygons efficiently, each with different trade-offs in terms of preprocessing time, query time, and space complexity. Although there are many applications that require computing these polygons such as computer graphics, robot motion planning, and network communication systems, there is a lack of any implementations of these algorithms in the literature - not to mention one that is exact, robust, and scalable. Furthermore, weak segment visibility polygons are used as basic building blocks in several other algorithms, such as in minimum-link path computation. In this work, we present an implementation of an optimal linear-time algorithm for computing the weak visibility polygon of a segment inside a triangulated simple polygon. Our implementation provides exact, robust geometric primitives and optimizations to handle large inputs with more than 18,000,000 vertices. We demonstrate two concrete applications: (1) construction of window partitions, a standard data structure in visibility algorithms, and (2) support for optimal minimum-link path queries between two points in a simple polygon, the latter serving as a direct use case of the former. Experimental results on a variety of polygon families confirm that the end-to-end running time scales linearly with the size of the polygon and is dominated by the cost of computing the triangulation, validating the practicality and scalability of the approach. The implementation is released as open source in the format of a CGAL package to support reproducibility and further research.
Cite as

Sándor P. Fekete, Prahlad Narasimhan Kasthurirangan, Phillip Keldenich, Fabian Kollhoff, Chek-Manh Loi, and Michael Perk. Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.45,
  author =	{Fekete, S\'{a}ndor P. and Kasthurirangan, Prahlad Narasimhan and Keldenich, Phillip and Kollhoff, Fabian and Loi, Chek-Manh and Perk, Michael},
  title =	{{Line Segment Visibility in Simple Polygons: Exact, Robust, Scalable Computation and Applications}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{45:1--45:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.45},
  URN =		{urn:nbn:de:0030-drops-258516},
  doi =		{10.4230/LIPIcs.SoCG.2026.45},
  annote =	{Keywords: Visibility, line segments, link distance, window partition, computation, implementation, robustness, scalability, exactness, CGAL}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.44
Tilt Automata: Gathering Particles with Uniform External Control

Authors: Sándor P. Fekete, Jonas Friemel, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the tiles of a polyomino with all particles reacting uniformly to an external force by moving as far as possible in one of the four axis-parallel directions until they hit the boundary. The goal is to choose a sequence of directions that moves all particles to a common position. Our results include a polynomial-time algorithm for gathering in a completely filled polyomino as well as hardness reductions for approximating shortest gathering sequences and for determining whether the particles in a partially filled polyomino can be gathered. We pay special attention to the impact of restricted geometry, particularly polyominoes without holes. As a corollary, we make progress on an open question from [Balanza-Martinez et al., SODA 2020] by showing that deciding whether a given position can be occupied remains NP-hard in polyominoes without holes. Our results build on a connection we establish between tilt models and the theory of synchronizing automata.
Cite as

Sándor P. Fekete, Jonas Friemel, Peter Kramer, Jan-Marc Reinhardt, Christian Rieck, and Christian Scheffer. Tilt Automata: Gathering Particles with Uniform External Control. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.44,
  author =	{Fekete, S\'{a}ndor P. and Friemel, Jonas and Kramer, Peter and Reinhardt, Jan-Marc and Rieck, Christian and Scheffer, Christian},
  title =	{{Tilt Automata: Gathering Particles with Uniform External Control}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{44:1--44:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.44},
  URN =		{urn:nbn:de:0030-drops-258508},
  doi =		{10.4230/LIPIcs.SoCG.2026.44},
  annote =	{Keywords: Uniform control, gathering, full tilt, polyominoes, synchronizing automata}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.14
General Computation Using Slidable Tiles with Deterministic Global Forces

Authors: Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We study the computational power of the Full-Tilt model of motion planning, where slidable polyominos are moved maximally around a board by way of a sequence of directional "tilts." We focus on the deterministic scenario in which the tilts constitute a repeated clockwise rotation. We show that general-purpose computation is possible within this framework by providing a direct and efficient simulation of space-bounded Turing machines in which one computational step of the machine is simulated per O(1) rotations. We further show that the initial tape of the machine can be programmed by an initial tilt-sequence preceding the rotations. This result immediately implies new PSPACE-completeness results for the well-studied problems of occupancy (deciding if a given board location can be occupied by a tile), vacancy (deciding if a location can be emptied), relocation (deciding if a tile can be moved from one location to another), and reconfiguration (can a given board configuration be reconfigured into a second given configuration) that hold even for deterministically repeating tilt cycles such as rotations. All of our PSPACE-completeness results hold even when there is only a single domino in the system beyond singleton tiles. Following, we show that these results work in the Single-Step tilt model for larger constant cycles. We then investigate computational efficiency by showing a modification to implement a two-tape Turing machine in the Full-Tilt model and Systolic Arrays in the Single-Step model. Finally, we show a cyclic implementation for tilt-efficient Threshold Circuits.
Cite as

Alberto Avila-Jimenez, David Barreda, Sarah-Laurie Evans, Austin Luchsinger, Aiden Massie, Robert Schweller, Evan Tomai, and Tim Wylie. General Computation Using Slidable Tiles with Deterministic Global Forces. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{avilajimenez_et_al:LIPIcs.ITCS.2026.14,
  author =	{Avila-Jimenez, Alberto and Barreda, David and Evans, Sarah-Laurie and Luchsinger, Austin and Massie, Aiden and Schweller, Robert and Tomai, Evan and Wylie, Tim},
  title =	{{General Computation Using Slidable Tiles with Deterministic Global Forces}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{14:1--14:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.14},
  URN =		{urn:nbn:de:0030-drops-253019},
  doi =		{10.4230/LIPIcs.ITCS.2026.14},
  annote =	{Keywords: motion planning, global control, external forces, deterministic computation, occupancy, vacancy}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.31
Delaunay Triangulations with Predictions

Authors: Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We investigate algorithms with predictions in computational geometry, specifically focusing on the basic problem of computing 2D Delaunay triangulations. Given a set P of n points in the plane and a triangulation G that serves as a "prediction" of the Delaunay triangulation, we would like to use G to compute the correct Delaunay triangulation DT(P) more quickly when G is "close" to DT(P). We obtain a variety of results of this type, under different deterministic and probabilistic settings, including the following: 1) Define D to be the number of edges in G that are not in DT(P). We present a deterministic algorithm to compute DT(P) from G in O(n + Dlog³ n) time, and a randomized algorithm in O(n+Dlog n) expected time, the latter of which is optimal in terms of D. 2) Let R be a random subset of the edges of DT(P), where each edge is chosen independently with probability ρ. Suppose G is any triangulation of P that contains R. We present an algorithm to compute DT(P) from G in O(nlog log n + nlog(1/ρ)) time with high probability. 3) Define d_{vio} to be the maximum number of points of P strictly inside the circumcircle of a triangle in G (the number is 0 if G is equal to DT(P)). We present a deterministic algorithm to compute DT(P) from G in O(nlog^*n + nlog d_{vio}) time. We also obtain results in similar settings for related problems such as 2D Euclidean minimum spanning trees, and hope that our work will open up a fruitful line of future research.
Cite as

Sergio Cabello, Timothy M. Chan, and Panos Giannopoulos. Delaunay Triangulations with Predictions. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 31:1-31:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cabello_et_al:LIPIcs.ITCS.2026.31,
  author =	{Cabello, Sergio and Chan, Timothy M. and Giannopoulos, Panos},
  title =	{{Delaunay Triangulations with Predictions}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{31:1--31:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.31},
  URN =		{urn:nbn:de:0030-drops-253186},
  doi =		{10.4230/LIPIcs.ITCS.2026.31},
  annote =	{Keywords: Delaunay Triangulation, Minimum Spanning Tree, Algorithms with Predictions}
}
Document
DOI: 10.4230/DagRep.15.5.64
Computational Geometry (Dagstuhl Seminar 25201)

Authors: Maarten Löffler, Eunjin Oh, Jeff M. Phillips, and Alexandra Weinberger

Published in: Dagstuhl Reports, Volume 15, Issue 5 (2025)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 25201 "Computational Geometry". The seminar program spanned the days from 11th May to 16th May 2025, and 39 participants from various countries were on site. Recent advances in computational geometry were presented and discussed, and new challenges were identified, in particular in relation to the two themes "parameterized complexity" and "the interplay between theory and implementation". This report collects the abstracts of the talks and the open problems presented at the seminar, an excerpt from the panel discussion, and partial progress from the active working groups.
Cite as

Maarten Löffler, Eunjin Oh, Jeff M. Phillips, and Alexandra Weinberger. Computational Geometry (Dagstuhl Seminar 25201). In Dagstuhl Reports, Volume 15, Issue 5, pp. 64-95, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@Article{loffler_et_al:DagRep.15.5.64,
  author =	{L\"{o}ffler, Maarten and Oh, Eunjin and Phillips, Jeff M. and Weinberger, Alexandra},
  title =	{{Computational Geometry (Dagstuhl Seminar 25201)}},
  pages =	{64--95},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2025},
  volume =	{15},
  number =	{5},
  editor =	{L\"{o}ffler, Maarten and Oh, Eunjin and Phillips, Jeff M. and Weinberger, Alexandra},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.15.5.64},
  URN =		{urn:nbn:de:0030-drops-252780},
  doi =		{10.4230/DagRep.15.5.64},
  annote =	{Keywords: algorithms, combinatorics, complexity, geometric computing, implementation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.6
A Dimension-Reducing Fréchet Simplification Oracle

Authors: Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
Let P be a polygonal curve with n vertices in the plane. We construct a data structure of size O(n log n) suited for simplification queries of the following kind. Given a query line 𝓁 and an integer k ≥ 1, find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to P, among all such curves. Using our data structure, a query can be handled in O(k² log³ n + k log⁴n) time. More generally, a geometric tree T on n vertices in the plane can be preprocessed into a near-linear-size structure so that, given a pair u, v of its vertices, a line 𝓁, and an integer k ≥ 1, one can find a curve Q on 𝓁 with at most k vertices that minimizes the discrete Fréchet distance to the path from u to v in T, in time O(k² polylog n). For the general dimension-reduction problem, where P is a curve in ℝ^d (d ≥ 3), 0 < ε₀ < 1 is a real parameter, and a query specifies a g-flat h (1 ≤ g ≤ d-1) and an integer k ≥ 1, we construct a data structure of size O(nlog n + f(ε₀) n), where f(ε₀) = (1+1/ε₀)^{(d-1)/2}, that allows us to find a curve Q on h with at most k vertices, whose discrete Fréchet distance to P is at most 1+ε₀ times the distance of Q^* to P, where Q^* is such a curve that minimizes the distance to P. The query handling time is O(f(ε₀) k² log² n).
Cite as

Boris Aronov, Tsuri Farhana, Matthew J. Katz, and Indu Ramesh. A Dimension-Reducing Fréchet Simplification Oracle. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aronov_et_al:LIPIcs.ISAAC.2025.6,
  author =	{Aronov, Boris and Farhana, Tsuri and Katz, Matthew J. and Ramesh, Indu},
  title =	{{A Dimension-Reducing Fr\'{e}chet Simplification Oracle}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.6},
  URN =		{urn:nbn:de:0030-drops-249149},
  doi =		{10.4230/LIPIcs.ISAAC.2025.6},
  annote =	{Keywords: Computational geometry, discrete Fr\'{e}chet distance, curve simplification oracle, restricted minimum enclosing disk queries}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.50
Reeb Lobsters Are 1-Planar (Poster Abstract)

Authors: Maarten Löffler, Miriam Münch, and Ignaz Rutter

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
Very recently, Chambers, Fasy, Hosseini Sereshgi and Löffler [Erin W. Chambers et al., 2025] showed that every Reeb caterpillar admits a crossing-free drawing. It turns out that this does not hold for Reeb lobsters but we show that these graphs admit drawings with at most one crossing per edge.
Cite as

Maarten Löffler, Miriam Münch, and Ignaz Rutter. Reeb Lobsters Are 1-Planar (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 50:1-50:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.GD.2025.50,
  author =	{L\"{o}ffler, Maarten and M\"{u}nch, Miriam and Rutter, Ignaz},
  title =	{{Reeb Lobsters Are 1-Planar}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{50:1--50:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.50},
  URN =		{urn:nbn:de:0030-drops-250365},
  doi =		{10.4230/LIPIcs.GD.2025.50},
  annote =	{Keywords: Reeb graphs, layered drawings, local crossing number}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.44
Recovering Graphs from Their Witness Unit Square Representation (Poster Abstract)

Authors: Maarten Löffler, Frank Staals, and Soeren Terziadis

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A wUSR of a graph G is a set of unit squares in the plane, one per vertex, if two vertices have an edge in G if their squares overlap and the overlap contains no witness. We present an output sensitive algorithm to compute a graph G based on its given witness unit square representation.
Cite as

Maarten Löffler, Frank Staals, and Soeren Terziadis. Recovering Graphs from Their Witness Unit Square Representation (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 44:1-44:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{loffler_et_al:LIPIcs.GD.2025.44,
  author =	{L\"{o}ffler, Maarten and Staals, Frank and Terziadis, Soeren},
  title =	{{Recovering Graphs from Their Witness Unit Square Representation}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{44:1--44:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.44},
  URN =		{urn:nbn:de:0030-drops-250306},
  doi =		{10.4230/LIPIcs.GD.2025.44},
  annote =	{Keywords: proximity graphs, geometric intersection graphs, witness representation, unit square intersection graph, output sensitive algorithm, range searching}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.36
Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces

Authors: Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We study reconfiguration in curve arrangements, where a subset of the crossings are marked as switches which have three possible states, and the goal is to set the switches such that the resulting curve arrangement has few self-intersections, or few faces that are incident to the same curve multiple times (a.k.a. popular faces). Our results are that these problems are NP-hard, but FPT in the number of switches. Minimizing self-intersections is also FPT in the number of non-switchable crossings; for minimizing popular faces this problem remains open. Our results can be applied to generating curved nonograms, a type of logic puzzle that has received some attention lately. Specifically, our results make it possible to efficiently convert expert puzzles into advanced puzzles (or determine that this is impossible).
Cite as

Florestan Brunck, Hsien-Chih Chang, Maarten Löffler, Tim Ophelders, and Lena Schlipf. Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brunck_et_al:LIPIcs.GD.2025.36,
  author =	{Brunck, Florestan and Chang, Hsien-Chih and L\"{o}ffler, Maarten and Ophelders, Tim and Schlipf, Lena},
  title =	{{Reconfiguration in Curve Arrangements to Reduce Self-Intersections and Popular Faces}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{36:1--36:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.36},
  URN =		{urn:nbn:de:0030-drops-250220},
  doi =		{10.4230/LIPIcs.GD.2025.36},
  annote =	{Keywords: Curve Arrangements, Reconfiguration, Curve Arrangements, NP-hardness, Fixed-Parameter Tractability, Puzzle Generation}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2025.51
Graph Tiles (Poster Abstract)

Authors: Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer, Alexandra Weinberger, and Carola Wenk

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We define a graph tile to be a unit square (or more generally, a polygon) on which a piece of a graph has been drawn/embedded; in particular, it may have vertices in its interior, edges connecting those vertices, or half-edges that extend to the boundary of the tile. In a graph tiling problem, we are given as input a set of graph tiles, with multiplicities, and the output is an arrangement of those tiles forming a graph of larger area. We focus on a simple tile set: unit square tiles with a central vertex and either a half-edge or no half-edge on each side. Up to symmetry this gives us six different types. We characterize which multiplicities are compatible for sets of at most three different tiles.
Cite as

Oswin Aichholzer, Robert Ganian, Phillip Keldenich, Maarten Löffler, Gert Meijer, Alexandra Weinberger, and Carola Wenk. Graph Tiles (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 51:1-51:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.51,
  author =	{Aichholzer, Oswin and Ganian, Robert and Keldenich, Phillip and L\"{o}ffler, Maarten and Meijer, Gert and Weinberger, Alexandra and Wenk, Carola},
  title =	{{Graph Tiles}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{51:1--51:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.51},
  URN =		{urn:nbn:de:0030-drops-250371},
  doi =		{10.4230/LIPIcs.GD.2025.51},
  annote =	{Keywords: graph tiles}
}
  • Refine by Type
  • 70 Document/PDF
  • 34 Document/HTML

  • Refine by Publication Year
  • 9 2026
  • 24 2025
  • 4 2024
  • 2 2023
  • 6 2022
  • Show More...

  • Refine by Author
  • 41 Löffler, Maarten
  • 13 Staals, Frank
  • 8 van der Hoog, Ivor
  • 7 Buchin, Kevin
  • 7 Kostitsyna, Irina
  • Show More...

  • Refine by Series/Journal
  • 64 LIPIcs
  • 1 OASIcs
  • 4 DagRep
  • 1 DagSemProc

  • Refine by Classification
  • 44 Theory of computation → Computational geometry
  • 8 Theory of computation → Design and analysis of algorithms
  • 3 Mathematics of computing → Graph algorithms
  • 3 Mathematics of computing → Graphs and surfaces
  • 2 Mathematics of computing → Discrete mathematics
  • Show More...

  • Refine by Keyword
  • 8 Fréchet distance
  • 4 computational geometry
  • 3 Fréchet Distance
  • 3 NP-hardness
  • 3 Reconfiguration
  • 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