research
∙
03/01/2023
Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity
We study a fundamental NP-hard motion coordination problem for multi-rob...
share
research
∙
11/02/2022
Partitioning a Polygon Into Small Pieces
We study the problem of partitioning a given simple polygon P into a min...
research
∙
08/15/2022
Degree of Convexity and Expected Distances in Polygons
We present an algorithm for computing the so-called Beer-index of a poly...
research
∙
12/07/2021
Online Sorting and Translational Packing of Convex Polygons
We investigate various online packing problems in which convex polygons ...
research
∙
08/10/2021
Distinguishing classes of intersection graphs of homothets or similarities of two convex disks
For smooth convex disks A, i.e., convex compact subsets of the plane wit...
research
∙
08/05/2021
Geometric Embeddability of Complexes is ∃ℝ-complete
We show that the decision problem of determining whether a given (abstra...
research
∙
06/04/2021
Covering Polygons is Even Harder
In the MINIMUM CONVEX COVER (MCC) problem, we are given a simple polygon...
research
∙
03/17/2021
Chasing Puppies: Mobile Beacon Routing on Closed Curves
We solve an open problem posed by Michael Biro at CCCG 2013 that was ins...
research
∙
02/19/2021
Training Neural Networks is ER-complete
Given a neural network, training data, and a threshold, it was known tha...
research
∙
01/22/2021
Online Packing to Minimize Area or Perimeter
We consider online packing problems where we get a stream of axis-parall...
research
∙
12/21/2020
Escaping an Infinitude of Lions
We consider the following game played in the Euclidean plane: There is a...
research
∙
11/22/2020
Tiling with Squares and Packing Dominos in Polynomial Time
We consider planar tiling and packing problems with polyomino pieces and...
research
∙
04/16/2020
Framework for ∃ℝ-Completeness of Two-Dimensional Packing Problems
We show that many natural two-dimensional packing problems are algorithm...
research
∙
12/18/2019
Dynamic Toolbox for ETRINV
Recently, various natural algorithmic problems have been shown to be ∃R-...
research
∙
09/02/2019
Disks in Curves of Bounded Convex Curvature
We say that a simple, closed curve γ in the plane has bounded convex cur...
research
∙
02/11/2019
Geometric Multicut
We study the following separation problem: Given a collection of colored...
research
∙
02/05/2019
Classifying Convex Bodies by their Contact and Intersection Graphs
Suppose that A is a convex body in the plane and that A_1,...,A_n are tr...
research
∙
03/31/2018
Fast Fencing
We consider very natural "fence enclosure" problems studied by Capoyleas...
research
∙
05/17/2017