11 citations · 16 across the 11 of their papers we have counts for
14 papers · 1 filter
Restless Guards: Robust Guarding of Polyominoes
Linda Kleist, Ramin Kosfeld, Christian Rieck
The art gallery problem is a fundamental problem whose practical applications have inspired numerous variants. In this work, we investigate a setting in which full coverage of the…
The Complexity of Recognizing Geometric Hypergraphs
Daniel Bertschinger, Nicolas El Maalouly, Linda Kleist +2
As set systems, hypergraphs are omnipresent and have various representations ranging from Euler and Venn diagrams to contact representations. In a geometric representation of a hyp…
Folding Polyiamonds into Octahedra
Eva Stehr, Linda Kleist
We study polyiamonds (polygons arising from the triangular grid) that fold into the smallest yet unstudied platonic solid -- the octahedron. We show a number of results. Firstly, w…
The Complexity of the Hausdorff Distance
Paul Jungeblut, Linda Kleist, Tillmann Miltzow
We investigate the computational complexity of computing the Hausdorff distance. Specifically, we show that the decision problem of whether the Hausdorff distance of two semi-algeb…
Online Sorting and Translational Packing of Convex Polygons
Anders Aamand, Mikkel Abrahamsen, Lorenzo Beretta +1
We investigate several online packing problems in which convex polygons arrive one by one and have to be placed irrevocably into a container, while the aim is to minimize the used…
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…
Adjacency Graphs of Polyhedral Surfaces
Elena Arseneva, Linda Kleist, Boris Klemz +4
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in . We show that every graph is realizable as a p…
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…
Upward Point Set Embeddings of Paths and Trees
Elena Arseneva, Pilar Cano, Linda Kleist +4
We study upward planar straight-line embeddings (UPSE) of directed trees on given point sets. The given point set has size at least the number of vertices in the tree. For the…
Competitive Location Problems: Balanced Facility Location and the One-Round Manhattan Voronoi Game
Thomas Byrne, Sándor P. Fekete, Jörg Kalcsics +1
We study competitive location problems in a continuous setting, in which facilities have to be placed in a rectangular domain of normalized dimensions of and , and…
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…
Folding Polyominoes with Holes into a Cube
Oswin Aichholzer, Hugo A. Akitaya, Kenneth C. Cheung +9
When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present s…
On the Area-Universality of Triangulations
Linda Kleist
We study straight-line drawings of planar graphs with prescribed face areas. A plane graph is 'area-universal' if for every area assignment on the inner faces, there exists a strai…
Completeness for the Complexity Class and Area-Universality
Michael G. Dobbins, Linda Kleist, Tillmann Miltzow +1
Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class plays a crucial role in the study of geometric problems.…