14 citations · 20 across the 13 of their papers we have counts for
23 papers
Matching with Multiple Bottlenecks: Parameterized Complexity and Approximation
Jonas Friemel, Tilo Hoitz, Phillip Keldenich +1
We consider a matching problem in which the cost of each edge is a vector with components. The cost of a matching is the sum of the bottlenecks over all components, and we ask…
Efficient Heuristics and Exact Methods for Pairwise Interaction Sampling
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We consider a class of optimization problems that are fundamental to testing in modern configurable software systems, e.g., in automotive industries. In pairwise interaction sampli…
Minimum Non-Obtuse Triangulations: The CG:SHOP Challenge 2025
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We give an overview of the 2025 Computational Geometry Challenge targeting the problem Minimum Non-Obtuse Triangulation: Given a planar straight-line graph G in the plane, defined…
Exact Algorithms for Minimum Dilation Triangulation
Sándor P. Fekete, Phillip Keldenich, Michael Perk
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…
How Low Can We Go? Minimizing Interaction Samples for Configurable Systems
Dominik Krupke, Ahmad Moradi, Michael Perk +5
Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality…
Targeted Drug Delivery: Algorithmic Methods for Collecting a Swarm of Particles with Uniform External Forces
Aaron T. Becker, Sándor P. Fekete, Li Huang +5
We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of mic…
Maximum Polygon Packing: The CG:SHOP Challenge 2024
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We give an overview of the 2024 Computational Geometry Challenge targeting the problem \textsc{Maximum Polygon Packing}: Given a convex region in the plane, and a collection of…
Minimum Coverage by Convex Polygons: The CG:SHOP Challenge 2023
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We give an overview of the 2023 Computational Geometry Challenge targeting the problem Minimum Coverage by Convex Polygons, which consists of covering a given polygonal region (pos…
Minimum Partition into Plane Subgraphs: The CG:SHOP Challenge 2022
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
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 segm…
Area-Optimal Simple Polygonalizations: The CG Challenge 2019
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich +2
We give an overview of theoretical and practical aspects of finding a simple polygon of minimum (Min-Area) or maximum (Max-Area) possible area for a given set of n points in the pl…
Computing Area-Optimal Simple Polygonizations
Sándor P. Fekete, Andreas Haas, Phillip Keldenich +2
We consider methods for finding a simple polygon of minimum (Min-Area) or maximum (Max-Area) possible area for a given set of points in the plane. Both problems are known to be NP-…
Connected Coordinated Motion Planning with Bounded Stretch
Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld +2
We consider the problem of connected coordinated motion planning for a large collective of simple, identical robots: From a given start grid configuration of robots, we need to rea…
Computing Coordinated Motion Plans for Robot Swarms: The CG:SHOP Challenge 2021
Sándor P. Fekete, Phillip Keldenich, Dominik Krupke +1
We give an overview of the 2021 Computational Geometry Challenge, which targeted the problem of optimally coordinating a set of robots by computing a family of collision-free traje…
Packing Squares into a Disk with Optimal Worst-Case Density
Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja +3
We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $δ=\frac{8}{5π}\a…
Computing Convex Partitions for Point Sets in the Plane: The CG:SHOP Challenge 2020
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich +2
We give an overview of the 2020 Computational Geometry Challenge, which targeted the problem of partitioning the convex hull of a given planar point set P into the smallest number…
Worst-Case Optimal Covering of Rectangles by Disks
Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich +2
We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any $λ\geq…
Parallel Online Algorithms for the Bin Packing Problem
Sándor P. Fekete, Jonas Grosse-Holz, Phillip Keldenich +1
We study \emph{parallel} online algorithms: For some fixed integer , a collective of parallel processes that perform online decisions on the same sequence of events forms a…
Packing Disks into Disks with Optimal Worst-Case Density
Sándor P. Fekete, Phillip Keldenich, Christian Scheffer
We provide a tight result for a fundamental problem arising from packing disks into a circular container: The critical density of packing disks in a disk is 0.5. This implies that…
CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata
Sándor P. Fekete, Robert Gmyr, Sabrina Hugo +3
We contribute results for a set of fundamental problems in the context of programmable matter by presenting algorithmic methods for evaluating and manipulating a collective of part…
Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch
Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich +2
We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, conti…
Tilt Assembly: Algorithms for Micro-Factories That Build Objects with Uniform External Forces
Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich +4
We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of prog…
Conflict-Free Coloring of Intersection Graphs
Sándor P. Fekete, Phillip Keldenich
A conflict-free -coloring of a graph assigns one of different colors to some of the vertices such that, for every vertex , there is a color that is assigned to…
Conflict-Free Coloring of Planar Graphs
Zachary Abel, Victor Alvarez, Aman Gour +5
A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vert…