19 citations · 26 across the 16 of their papers we have counts for
15 papers · 1 filter
Guarding Offices with Maximum Dispersion
Sándor P. Fekete, Kai Kobbe, Dominik Krupke +3
We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (-visibility) for a class of orthogonal polygons that reflect the properties of r…
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…
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…
The Lawn Mowing Problem: From Algebra to Algorithms
Sándor P. Fekete, Dominik Krupke, Michael Perk +2
For a given polygonal region , the Lawn Mowing Problem (LMP) asks for a shortest tour that gets within Euclidean distance 1/2 of every point in ; this is equivalent to co…
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…
A Closer Cut: Computing Near-Optimal Lawn Mowing Tours
Sándor P. Fekete, Dominik Krupke, Michael Perk +2
For a given polygonal region , the Lawn Mowing Problem (LMP) asks for a shortest tour that gets within Euclidean distance 1 of every point in ; this is equivalent to comp…
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 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…
Minimum Scan Cover and Variants -- Theory and Experiments
Kevin Buchin, Sándor P. Fekete, Alexander Hill +5
We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Cos…
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…
Probing a Set of Trajectories to Maximize Captured Information
Sándor P. Fekete, Alexander Hill, Dominik Krupke +4
We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set of trajectories in the plane, and an integer $k\geq…
Minimum Scan Cover with Angular Transition Costs
Sándor P. Fekete, Linda Kleist, Dominik Krupke
We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. In the problem Minim…
Computing Nonsimple Polygons of Minimum Perimeter
Sándor P. Fekete, Andreas Haas, Michael Hemmer +8
We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertic…