Publications

2024

1. 

   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.

2. 

   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.

2023

1. 

   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.

2. 

   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.

3. 

   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

1. 

   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.

2. 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
3. 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
4. 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

5. 

   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

1. 

   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.

2. 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

1. 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
2. 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
3. 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

4. 

   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
5. 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
6. 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

1. 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

2. 

   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.

3. 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

4. 

   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

1. 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
2. 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

1. 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
2. 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
3. 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
4. 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

1. Algorithmic methods for complex dynamic sweeping problems

   Dominik Krupke

   Oct 2016
2. 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
3. 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

1. 

   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
2. 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

1. Distributed, scalable algorithmic methods for swarms with multiple leader robots

   Maximilian Ernestus ,  and  Dominik Krupke

   Oct 2014
2. 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