Publications | Dominik Michael Krupke

2024

Edge Sparsification for Geometric Tour Problems

Sándor Fekete , Phillip Keldenich , Dominik Krupke , and Eike Niehs

Computing in Geometry and Topology, Jan 2024

Abs

We study a variety of sparsification approaches for a spectrum of geometric optimization problems related to tour problems, such as the Angular TSP, the Minimum Perimeter Problem, and the Minimum/Maximum Area Polygon Problem. To this end, we conduct a thorough study that compares the solution quality and runtime achieved by integer programming solvers on geometrically reduced edge sets to the exact solution on the full edge set; considered sparsification techniques include a variety of triangulations (Delaunay, Greedy, Minimum Weight), Theta and Yao graphs, Well-Separated Pair Decomposition, and Onion graphs.
Near-Optimal Coverage Path Planning with Turn Costs

Dominik Krupke

In 2024 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , Jan 2024

Abs

Coverage path planning is a fundamental challenge in robotics, with diverse applications in aerial surveillance, manufacturing, cleaning, inspection, agriculture, and more. The main objective is to devise a trajectory for an agent that efficiently covers a given area, while minimizing time or energy consumption. Existing practical approaches often lack a solid theoretical foundation, relying on purely heuristic methods, or overly abstracting the problem to a simple Traveling Salesman Problem in Grid Graphs. Moreover, the considered cost functions only rarely consider turn cost, prize-collecting variants for uneven cover demand, or arbitrary geometric regions. In this paper, we describe an array of systematic methods for handling arbitrary meshes derived from intricate, polygonal environments. This adaptation paves the way to compute efficient coverage paths with a robust theoretical foundation for real-world robotic applications. Through comprehensive evaluations, we demonstrate that the algorithm also exhibits low optimality gaps, while efficiently handling complex environments. Furthermore, we showcase its versatility in handling partial coverage and accommodating heterogeneous passage costs, offering the flexibility to trade off coverage quality and time efficiency.
What Goes Around Comes Around: Covering Tours and Cycle Covers with Turn Costs

Sándor P Fekete , and Dominik Krupke

Theory of Computing Systems, Jan 2024

Abs

We investigate several geometric problems of finding tours and cycle covers with minimum turn cost, which have been studied in the past, with complexity, approximation results, and open problems dating back to work by Arkin et al. in 2001. Many new practical applications have spawned variants: For full coverage, all points have to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring a penalty. We show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and O’Rourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. We also provide a number of positive results. In particular, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants for grid-based instances, based on LP/IP techniques. These geometric versions allow many possible edge directions (and thus, turn angles, such as in hexagonal grids or higher-dimensional variants); our approximation factors improve the combinatorial ones of Arkin et al.

2023

The Lawn Mowing Problem: From Algebra to Algorithms

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

In 31st Annual European Symposium on Algorithms (ESA 2023) , Jan 2023

Abs

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.
A Closer Cut: Computing Near-Optimal Lawn Mowing Tours

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

In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX) , Jan 2023

Abs

For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1 of every point in P; this is equivalent to computing a shortest tour for a unit-disk cutter C that covers all of P. As a geometric optimization problem of natural practical and theoretical importance, the LMP generalizes and combines several notoriously difficult problems, including minimum covering by disks, the Traveling Salesman Problem with neighborhoods (TSPN), and the Art Gallery Problem (AGP). In this paper, we conduct the first study of the Lawn Mowing Problem with a focus on practical computation of near-optimal solutions. We provide new theoretical insights: Optimal solutions are polygonal paths with a bounded number of vertices, allowing a restriction to straight-line solutions; on the other hand, there can be relatively simple instances for which optimal solutions require a large class of irrational coordinates. On the practical side, we present a primal-dual approach with provable convergence properties based on solving a special case of the TSPN restricted to witness sets. In each iteration, this establishes both a valid solution and a valid lower bound, and thereby a bound on the remaining optimality gap. As we demonstrate in an extensive computational study, this allows us to achieve provably optimal and near-optimal solutions for a large spectrum of benchmark instances with up to 2000 vertices.
Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022

Sándor P. Fekete , Phillip Keldenich , Dominik Krupke , and Stefan Schirra

ACM J. Exp. Algorithmics, Aug 2023

Abs

We give an overview of the 2022 Computational Geometry Challenge targeting the problem Minimum Partition into Plane Subsets, which consists of partitioning a given set of line segments into a minimum number of non-crossing subsets.

2022

Robust disease module mining via enumeration of diverse prize-collecting Steiner trees

Judith Bernett , Dominik Krupke , Sepideh Sadegh , Jan Baumbach , Sándor P. Fekete , Tim Kacprowski , Markus List , and David B. Blumenthal

Bioinformatics, Jan 2022

Abs

Disease module mining methods (DMMMs) extract subgraphs that constitute candidate disease mechanisms from molecular interaction networks such as protein–protein interaction (PPI) networks. Irrespective of the employed models, DMMMs typically include non-robust steps in their workflows, i.e. the computed subnetworks vary when running the DMMMs multiple times on equivalent input. This lack of robustness has a negative effect on the trustworthiness of the obtained subnetworks and is hence detrimental for the widespread adoption of DMMMs in the biomedical sciences. To overcome this problem, we present a new DMMM called ROBUST (robust disease module mining via enumeration of diverse prize-collecting Steiner trees). In a large-scale empirical evaluation, we show that ROBUST outperforms competing methods in terms of robustness, scalability and, in most settings, functional relevance of the produced modules, measured via KEGG (Kyoto Encyclopedia of Genes and Genomes) gene set enrichment scores and overlap with DisGeNET disease genes.
Minimum Scan Cover and Variants: Theory and Experiments

Kevin Buchin , Alexander Hill , Sándor Fekete , Linda Kleist , Irina Kostitsyna , Dominik Krupke , Roel Lambers , and Martijn Struijs

ACM Journal of Experimental Algorithmics, Jan 2022
Computing coordinated motion plans for robot swarms: The cg: shop challenge 2021

Sándor P Fekete , Phillip Keldenich , Dominik Krupke , and Joseph SB Mitchell

ACM Journal of Experimental Algorithmics (JEA), Jan 2022
Area-optimal simple polygonalizations: The CG challenge 2019

Erik D Demaine , Sándor P Fekete , Phillip Keldenich , Dominik Krupke , and Joseph SB Mitchell

Journal of Experimental Algorithmics (JEA), Jan 2022
Algorithm Engineering for Hard Problems in Computational Geometry

Dominik Michael Krupke

May 2022

Abs

Many practically relevant problems in Computational Geometry are provably hard to solve. In this thesis, we consider a series of these problems and tackle them with techniques from algorithm engineering, e.g., mixed integer programming or deep reinforcement learning. Additionally, we provide a number of results on complexity and algorithms for these problems. We start with a set of problems occurring in the context of large satellite systems, where communication requires a rotation of directional antennas. Here, we discover a close relationship to the vertex coloring problem, use constraint programming to obtain optimal solutions, and provide a practical auction-based algorithm that achieves good results in a realistic simulation. Then we continue with (partial) coverage path planning problems involving turn costs, which require different approaches than when minimizing only the traveled distance. We engineer an approximation algorithm based on linear relaxation and minimum-weight perfect matching to solve large instances in grid graphs. This approach is then generalized to complex polygonal instances, which allow modeling of difficult real-world scenarios. Afterward, we focus on probing a set of trajectories to maximize the captured information, where we successfully apply mixed integer programming and a set of heuristics. We also consider robots so small they need to be actuated by external forces like a magnetic field; applications for such robots include cancer treatment. Construction plans for miniature objects are computed using SAT-solvers, and control sequences to gather a swarm of these robots are optimized using deep reinforcement learning. Finally, we close the thesis with an excursion in hosting the CG:SHOP competition for three years and counting.

2021

Minimum Scan Cover with Angular Transition Costs

Sándor P. Fekete , Linda Kleist , and Dominik Krupke

SIAM J. Discret. Math., May 2021

Abs

We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph \G that is embedded in Euclidean space. The edges of \G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. A real-world motivation arises in the context of satellite communication and astrophysics. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in \Θ(\log χ(G)) while for 3D the minimum scan time is not upper bounded by \χ(G)\. We use this relationship to prove that the existence of a constant-factor approximation implies P \= NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of \\frac32 even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an Ø(c)\-approximation for \k\-colored graphs with \k≤χ(G)^c\. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph.
Minimum Scan Cover and Variants - Theory and Experiments

Kevin Buchin , Sándor P. Fekete , Alexander Hill , Linda Kleist , Irina Kostitsyna , Dominik Krupke , Roel Lambers , and Martijn Struijs

In 19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France , May 2021

2020

Towards the Automated Operations of Large Distributed Satellite Systems. Part 1: Review and Paradigm Shifts

Mohamed Ben Larbi , Kattia Pozo , Tom Haylok , Mirue Choi , Benjamin Grzesik , Andreas Haas , Dominik Krupke , Harald Konstanski , Volker Schaus , Sándor Fekete , and 2 more authors

Advances in Space Research, Aug 2020
Towards the Automated Operations of Large Distributed Satellite Systems. Part 2: Classifications and Tools

Mohamed Ben Larbi , Kattia Pozo , Mirue Choi , Tom Haylok , Benjamin Grzesik , Andreas Haas , Dominik Krupke , Harald Konstanski , Volker Schaus , Sándor Fekete , and 2 more authors

Advances in Space Research, Sep 2020
Tilt Assembly: Algorithms for Micro-factories That Build Objects with Uniform External Forces

Aaron T. Becker , Sándor P. Fekete , Phillip Keldenich , Dominik Krupke , Christian Rieck , Christian Scheffer , and Arne Schmidt

Algorithmica, Sep 2020
Minimum Scan Cover with Angular Transition Costs

Sándor P. Fekete , Linda Kleist , and Dominik Krupke

In 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland , Sep 2020
Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform, External Forces

Aaron T. Becker , Sándor P. Fekete , Li Huang , Phillip Keldenich , Linda Kleist , Dominik Krupke , Christian Rieck , and Arne Schmidt

In 2020 IEEE International Conference on Robotics and Automation, ICRA 2020, Paris, France, May 31 - August 31, 2020 , Sep 2020
Probing a Set of Trajectories to Maximize Captured Information

Sándor P. Fekete , Alexander Hill , Dominik Krupke , Tyler Mayer , Joseph S. B. Mitchell , Ojas Parekh , and Cynthia A. Phillips

In 18th International Symposium on Experimental Algorithms, SEA 2020, June 16-18, 2020, Catania, Italy , Sep 2020

2019

Automated Constellation Management With Self-Regulating Data-Economic Actors

Volker Schaus , Dominik Krupke , Mohamed Ben Larbi , Andreas Haas , Benjamin Grzesik , Jonas Radtke , Sándor Fekete , and Enrico Stoll

In 70th International Astronautical Congress (IAC) , Oct 2019
Practical Methods for Computing Large Covering Tours and Cycle Covers with Turn Cost

Sándor P. Fekete , and Dominik Krupke

In Proceedings of the Twenty-First Workshop on Algorithm Engineering and Experiments, ALENEX 2019, San Diego, CA, USA, January 7-8, 2019 , Oct 2019

Abs

We study the problem of computing provably optimal and near-optimal solutions for the NP-hard problem of finding covering tours and cycle covers with turn cost, which are of practical importance for a variety of applications, such as pest control and precision farming. Previous work has largely focused on theoretical aspects, such as complexity and approximation. We develop a number of algorithm engineering techniques and refinements to make such theoretical insights practically useful, resulting in a comprehensive study for solving a wide spectrum of large instances. We compute provably optimal solutions for instances with more than 1000 pixels, from the largest previous solved instance size of 76 (de Assis and de Souza 2011). Making use of additional algorithm engineering techniques for handling very large instances, we also compute near-optimal solutions for instances with up to 300 000 pixels, for which we give solutions that are typically within a few percent of our computed lower bounds. We also provide an experimental comparison of a practically refined version of our new theoretical approach with the approximation technique of Arkin et al. that dates back to 2001; we show that our new LP/IP-based approximation method closes 70% of the remaining optimality gap to the lower bound.
Automated Data Retrieval from Large-Scale Distributed Satellite Systems

Dominik Krupke , Volker Schaus , Andreas Haas , Michael Perk , Jonas Dippel , Benjamin Grzesik , Mohamed Khalil Ben Larbi , Enrico Stoll , Tom Haylock , Harald Konstanski , and 4 more authors

In 15th IEEE International Conference on Automation Science and Engineering, CASE 2019, Vancouver, BC, Canada, August 22-26, 2019 , Oct 2019
Covering Tours and Cycle Covers with Turn Costs: Hardness and Approximation

Sándor P. Fekete , and Dominik Krupke

In Algorithms and Complexity - 11th International Conference, CIAC 2019, Rome, Italy, May 27-29, 2019, Proceedings , Oct 2019

Abs

We investigate a variety of geometric problems of finding tours and cycle covers with minimum turn cost, which have been studied in the past, with complexity and approximation results, and open problems dating back to work by Arkin et al. in 2001. Many new practical applications have spawned variants: For full coverage, every point has to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring a penalty. We make a number of contributions. We first show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and O’Rourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. On the positive side, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants for very general classes of instances, making use of LP/IP techniques. For these problems with many possible edge directions (and thus, turn angles, such as in hexagonal grids or higher-dimensional variants), our approximation factors also improve the combinatorial ones of Arkin et al. Our approach can also be extended to other geometric variants, such as scenarios with obstacles and linear combinations of turn and distance costs.

2018

Using a UAV for Destructive Surveys of Mosquito Population

An Nguyen , Dominik Krupke , Mary Burbage , Shriya Bhatnagar , Sándor P. Fekete , and Aaron T. Becker

In 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018 , Oct 2018
On Designing 2D Discrete Workspaces to Sort or Classify Polynminoes

Phillip Keldenich , Sheryl Manzoor , Li Huang , Dominik Krupke , Arne Schmidt , Sándor P. Fekete , and Aaron T. Becker

In 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2018, Madrid, Spain, October 1-5, 2018 , Oct 2018

2017

Computing nonsimple polygons of minimum perimeter

Sándor P. Fekete , Andreas Haas , Michael Hemmer , Michael Hoffmann , Irina Kostitsyna , Dominik Krupke , Florian Maurer , Joseph S. B. Mitchell , Arne Schmidt , Christiane Schmidt , and 1 more author

J. Comput. Geom., Oct 2017
Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)

Aaron T. Becker , Mustapha Debboun , Sándor P. Fekete , Dominik Krupke , and An Nguyen

In 33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia , Oct 2017
Mapping and coverage with a particle swarm controlled by uniform inputs

Arun Mahadev , Dominik Krupke , Sándor P. Fekete , and Aaron T. Becker

In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2017, Vancouver, BC, Canada, September 24-28, 2017 , Oct 2017
Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces

Aaron T. Becker , Sándor P. Fekete , Phillip Keldenich , Dominik Krupke , Christian Rieck , Christian Scheffer , and Arne Schmidt

In 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand , Oct 2017

2016

Algorithmic methods for complex dynamic sweeping problems

Dominik Krupke

Oct 2016
Collecting a swarm in a grid environment using shared, global inputs

Arun V. Mahadev , Dominik Krupke , Jan-Marc Reinhardt , Sándor P. Fekete , and Aaron T. Becker

In IEEE International Conference on Automation Science and Engineering, CASE 2016, Fort Worth, TX, USA, August 21-25, 2016 , Oct 2016
Computing Nonsimple Polygons of Minimum Perimeter

Sándor P. Fekete , Andreas Haas , Michael Hemmer , Michael Hoffmann , Irina Kostitsyna , Dominik Krupke , Florian Maurer , Joseph S. B. Mitchell , Arne Schmidt , Christiane Schmidt , and 1 more author

In Experimental Algorithms - 15th International Symposium, SEA 2016, St. Petersburg, Russia, June 5-8, 2016, Proceedings , Oct 2016

2015

Distributed cohesive control for robot swarms: Maintaining good connectivity in the presence of exterior forces

Dominik Krupke , Maximilian Ernestus , Michael Hemmer , and Sándor P. Fekete

In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015, Hamburg, Germany, September 28 - October 2, 2015 , Oct 2015
A parallel distributed strategy for arraying a scattered robot swarm

Dominik Krupke , Michael Hemmer , James McLurkin , Yu Zhou , and Sándor P. Fekete

In 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS 2015, Hamburg, Germany, September 28 - October 2, 2015 , Oct 2015

2014

Distributed, scalable algorithmic methods for swarms with multiple leader robots

Maximilian Ernestus , and Dominik Krupke

Oct 2014
Panic Room: Experiencing Overload and Having Fun in the Process

Björn Bankowski , Thiemo Clausen , Dirk Ehmen , Maximilian Ernestus , Henning Hasemann , Tobias Jura , Alexander Kröller , Dominik Krupke , and Marco Nikander

In Distributed, Ambient, and Pervasive Interactions - Second International Conference, DAPI 2014, Held as Part of HCI Interational 2014, Heraklion, Crete, Greece, June 22-27, 2014. Proceedings , Oct 2014