11 citations · 16 across the 11 of their papers we have counts for
23 papers
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…
A solution to Ringel's circle problem
James Davies, Chaya Keller, Linda Kleist +2
We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. This provides a strong negative answer to Ringel's…
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…
Geometric Embeddability of Complexes is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
We show that the decision problem of determining whether a given (abstract simplicial) -complex has a geometric embedding in is complete for the Existential Theory…
The tripartite-circle crossing number of graphs with two small partition classes
Charles Camacho, Silvia Fernández-Merchant, Marija Jelić Milutinović +4
A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not…
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…
Training Neural Networks is -complete
Mikkel Abrahamsen, Linda Kleist, Tillmann Miltzow
Given a neural network, training data, and a threshold, it was known that it is NP-hard to find weights for the neural network such that the total error is below the threshold. We…
Scheduling with Machine Conflicts
Moritz Buchem, Linda Kleist, Daniel Schmidt genannt Waldschmidt
We study the scheduling problem of makespan minimization while taking machine conflicts into account. Machine conflicts arise in various settings, e.g., shared resources for pre- 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…
Bounding the tripartite-circle crossing number of complete tripartite graphs
Charles Camacho, Silvia Fernández-Merchant, Marija Jelić Milutinović +4
A tripartite-circle drawing of a tripartite graph is a drawing in the plane, where each part of a vertex partition is placed on one of three disjoint circles, and the edges do not…
On the edge-vertex ratio of maximal thrackles
Oswin Aichholzer, Linda Kleist, Boris Klemz +2
A drawing of a graph in the plane is a thrackle if every pair of edges intersects exactly once, either at a common vertex or at a proper crossing. Conway's conjecture states that a…
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…
Rainbow cycles in flip graphs
Stefan Felsner, Linda Kleist, Torsten Mütze +1
The flip graph of triangulations has as vertices all triangulations of a convex -gon, and an edge between any two triangulations that differ in exactly one edge. An -rainbow…
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.…
Upper and Lower Bounds on Long Dual-Paths in Line Arrangements
Udo Hoffmann, Linda Kleist, Tillmann Miltzow
Given a line arrangement with lines, we show that there exists a path of length in the dual graph of formed by its faces. This bound is tight u…