Search Results

Documents authored by Perk, Michael

Artifact
Software
DOI: 10.4230/artifacts.26083
tubs-alg/TSPN-SoCG-2026

Authors: Rouven Kniep, Dominik Krupke, and Michael Perk

Abstract
Cite as

Rouven Kniep, Dominik Krupke, Michael Perk. tubs-alg/TSPN-SoCG-2026 (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-26083,
   title = {{tubs-alg/TSPN-SoCG-2026}}, 
   author = {Kniep, Rouven and Krupke, Dominik and Perk, Michael},
   note = {Software, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:798ae47a3445f53c64575fac631a25a1921a137b;origin=https://github.com/tubs-alg/TSPN-SoCG-2026;visit=swh:1:snp:3bea888a00cf4298aeeef069f6c05b5d047cfe58;anchor=swh:1:rev:5ad58a04610165f58d7a73055aee1a2328ff0d95}{\texttt{swh:1:dir:798ae47a3445f53c64575fac631a25a1921a137b}} (visited on 2026-05-27)},
   url = {https://github.com/tubs-alg/TSPN-SoCG-2026},
   doi = {10.4230/artifacts.26083},
}
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.46
A Branch-And-Bound Algorithm for the Traveling Salesman Problem with Difficult Neighborhoods

Authors: Sándor P. Fekete, Rouven Kniep, Dominik Krupke, and Michael Perk

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

Abstract
The Traveling Salesman Problem with Neighborhoods (TSPN) generalizes the classical Traveling Salesman Problem (TSP) by requiring a tour to visit a set of polygonal regions rather than fixed points, a natural goal that arises in various applications. While the geometric TSP allows arbitrarily close approximation and provably optimal solutions for benchmark instances of significant size, the TSPN is considerably more challenging, both in theory (due to APX-hardness) and practice, for which only benchmark instances up to 16 regions have been solved to optimality. Here we present a branch-and-bound algorithm that combines a spectrum of geometry-based filters (for reducing the number of considered sequences) with Second-Order Cone Programs (SOCP) (for computing optimal tours for a given permutation of neighborhoods). This allows us to solve larger polygonal TSPN instances than before to within an optimality tolerance of 0.1%; moreover, while previous work (both in theory and practice) relied on relatively benign neighborhoods, we can handle non-convex, non-simple neighborhoods of different sizes. In experiments on 490 benchmark instances with up to 50 polygons each, our method achieves a 99.6% optimality rate within 300s, with the remaining two instances solved within 595s. For 68 larger instances of size n = 60, our method still allows solving 86.8% of instances to optimality within 900s, leaving only 3 of the instances with optimality gaps above 3%, with the maximum being 5.53%.
Cite as

Sándor P. Fekete, Rouven Kniep, Dominik Krupke, and Michael Perk. A Branch-And-Bound Algorithm for the Traveling Salesman Problem with Difficult Neighborhoods. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.46,
  author =	{Fekete, S\'{a}ndor P. and Kniep, Rouven and Krupke, Dominik and Perk, Michael},
  title =	{{A Branch-And-Bound Algorithm for the Traveling Salesman Problem with Difficult Neighborhoods}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{46:1--46: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.46},
  URN =		{urn:nbn:de:0030-drops-258529},
  doi =		{10.4230/LIPIcs.SoCG.2026.46},
  annote =	{Keywords: Geometric optimization, geometric covering, TSP with neighborhoods, exact algorithms, algorithm engineering}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.102
Tracking a Set of Moving Objects with Minimal Peak Power (Media Exposition)

Authors: Sándor P. Fekete, Malte Hoffmann, Chek-Manh Loi, and Michael Perk

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

Abstract
A common sensing problem is to use a set of stationary tracking locations to monitor a collection of moving devices. Given n objects that need to be tracked, each following its own trajectory, and m stationary traffic control stations, each with a sensing region that can be changed over time; how should we adjust the individual sensor ranges in order to optimize energy consumption? We illustrate how to combine geometric insights with mathematical optimization to find optimal solutions for the min max variant of the problem, which aims at minimizing peak power consumption. Instances with 500 moving objects and 25 stations can be solved in the order of seconds for scenarios that take minutes to play out in the real world, demonstrating real-time capability of our methods.
Cite as

Sándor P. Fekete, Malte Hoffmann, Chek-Manh Loi, and Michael Perk. Tracking a Set of Moving Objects with Minimal Peak Power (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 102:1-102:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.102,
  author =	{Fekete, S\'{a}ndor P. and Hoffmann, Malte and Loi, Chek-Manh and Perk, Michael},
  title =	{{Tracking a Set of Moving Objects with Minimal Peak Power}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{102:1--102:7},
  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.102},
  URN =		{urn:nbn:de:0030-drops-259087},
  doi =		{10.4230/LIPIcs.SoCG.2026.102},
  annote =	{Keywords: Set cover, kinetic problems, geometric optimization, exact optimization}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.103
Scalable Algorithmic Methods for Simulating Heavy-Rain Events (Media Exposition)

Authors: Sándor P. Fekete, Phillip Keldenich, Michael Perk, and Tobias Wallner

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

Abstract
We motivate and demonstrate simulation and evaluation of large-scale, fine-grained hydrodynamic flows, triggered by heavy-rain events. We show significant progress for simulating time-dependent, high-resolution runoff in large-scale heavy-rain scenarios, based on different geometry-based algorithmic speedup techniques. This enables us to address a second challenge: How can we deal with the instability of precipitation events, which are notoriously difficult to predict with good accuracy?
Cite as

Sándor P. Fekete, Phillip Keldenich, Michael Perk, and Tobias Wallner. Scalable Algorithmic Methods for Simulating Heavy-Rain Events (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 103:1-103:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2026.103,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Perk, Michael and Wallner, Tobias},
  title =	{{Scalable Algorithmic Methods for Simulating Heavy-Rain Events}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{103:1--103:6},
  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.103},
  URN =		{urn:nbn:de:0030-drops-259094},
  doi =		{10.4230/LIPIcs.SoCG.2026.103},
  annote =	{Keywords: Heavy-rain events, hydrodynamic flows, scalable simulation, applied computational geometry, sensitivity analysis}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.48
Exact Algorithms for Minimum Dilation Triangulation

Authors: Sándor P. Fekete, Phillip Keldenich, and Michael Perk

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

Abstract
We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable previous attention: Given a set P of n points in the plane, find a triangulation T, such that a shortest Euclidean path in T between any pair of points increases by the smallest possible factor compared to their straight-line distance. No polynomial-time algorithm is known for the problem; moreover, evaluating the objective function involves computing the sum of (possibly many) square roots. On the other hand, the problem is not known to be NP-hard. (1) We provide practically robust methods and implementations for computing an MDT for benchmark sets with up to 30,000 points in reasonable time on commodity hardware, based on new geometric insights into the structure of optimal edge sets. Previous methods only achieved results for up to 200 points, so we extend the range of optimally solvable instances by a factor of 150. (2) We develop scalable techniques for accurately evaluating many shortest-path queries that arise as large-scale sums of square roots, allowing us to certify exact optimal solutions, with previous work relying on (possibly inaccurate) floating-point computations. (3) We resolve an open problem by establishing a lower bound of 1.44116 on the dilation of the regular 84-gon (and thus for arbitrary point sets), improving the previous worst-case lower bound of 1.4308 and greatly reducing the remaining gap to the upper bound of 1.4482 from the literature. In the process, we provide optimal solutions for regular n-gons up to n = 100.
Cite as

Sándor P. Fekete, Phillip Keldenich, and Michael Perk. Exact Algorithms for Minimum Dilation Triangulation. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2025.48,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Perk, Michael},
  title =	{{Exact Algorithms for Minimum Dilation Triangulation}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{48:1--48:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.48},
  URN =		{urn:nbn:de:0030-drops-232006},
  doi =		{10.4230/LIPIcs.SoCG.2025.48},
  annote =	{Keywords: dilation, minimum dilation triangulation, exact algorithms, algorithm engineering, experimental evaluation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2023.45
The Lawn Mowing Problem: From Algebra to Algorithms

Authors: Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1/2 of every point in P; this is equivalent to computing a shortest tour for a unit-diameter cutter C that covers all of P. As a generalization of the Traveling Salesman Problem, the LMP is NP-hard; unlike the discrete TSP, however, the LMP has defied efforts to achieve exact solutions, due to its combination of combinatorial complexity with continuous geometry. We provide a number of new contributions that provide insights into the involved difficulties, as well as positive results that enable both theoretical and practical progress. (1) We show that the LMP is algebraically hard: it is not solvable by radicals over the field of rationals, even for the simple case in which P is a 2×2 square. This implies that it is impossible to compute exact optimal solutions under models of computation that rely on elementary arithmetic operations and the extraction of kth roots, and explains the perceived practical difficulty. (2) We exploit this algebraic analysis for the natural class of polygons with axis-parallel edges and integer vertices (i.e., polyominoes), highlighting the relevance of turn-cost minimization for Lawn Mowing tours, and leading to a general construction method for feasible tours. (3) We show that this construction method achieves theoretical worst-case guarantees that improve previous approximation factors for polyominoes. (4) We demonstrate the practical usefulness beyond polyominoes by performing an extensive practical study on a spectrum of more general benchmark polygons: We obtain solutions that are better than the previous best values by Fekete et al., for instance sizes up to 20 times larger.
Cite as

Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer. The Lawn Mowing Problem: From Algebra to Algorithms. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ESA.2023.45,
  author =	{Fekete, S\'{a}ndor P. and Krupke, Dominik and Perk, Michael and Rieck, Christian and Scheffer, Christian},
  title =	{{The Lawn Mowing Problem: From Algebra to Algorithms}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{45:1--45:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.45},
  URN =		{urn:nbn:de:0030-drops-186985},
  doi =		{10.4230/LIPIcs.ESA.2023.45},
  annote =	{Keywords: Geometric optimization, covering problems, tour problems, lawn mowing, algebraic hardness, approximation algorithms, algorithm engineering}
}
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