research
∙
03/01/2023
Towards Space Efficient Two-Point Shortest Path Queries in a Polygonal Domain
We devise a data structure that can answer shortest path queries for two...
share
research
∙
02/27/2023
The Complexity of Recognizing Geometric Hypergraphs
As set systems, hypergraphs are omnipresent and have various representat...
research
∙
01/09/2023
Representing Matroids over the Reals is ∃ℝ-complete
A matroid M is an ordered pair (E,I), where E is a finite set called the...
research
∙
12/02/2022
Sometimes Two Irrational Guards are Needed
In the art gallery problem, we are given a closed polygon P, with ration...
research
∙
08/13/2022
Avoider-Enforcer Game is NP-hard
In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enfo...
research
∙
04/04/2022
Training Fully Connected Neural Networks is ∃ℝ-Complete
We consider the algorithmic problem of finding the optimal weights and b...
research
∙
12/08/2021
The Complexity of the Hausdorff Distance
We investigate the computational complexity of computing the Hausdorff d...
research
∙
08/09/2021
Topological Art in Simple Galleries
Let P be a simple polygon, then the art gallery problem is looking for a...
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
On Classifying Continuous Constraint Satisfaction problems
A continuous constraint satisfaction problem (CCSP) is a constraint sati...
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/19/2021
Local Complexity of Polygons
Many problems in Discrete and Computational Geometry deal with simple po...
research
∙
09/30/2020
Between Shapes, Using the Hausdorff Distance
Given two shapes A and B in the plane with Hausdorff distance 1, is ther...
research
∙
07/14/2020
A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
Given a closed simple polygon P, we say two points p,q see each other if...
research
∙
04/16/2020
Framework for ∃ℝ-Completeness of Two-Dimensional Packing Problems
We show that many natural two-dimensional packing problems are algorithm...
research
∙
03/05/2020
Maximum Clique in Disk-Like Intersection Graphs
We study the complexity of Maximum Clique in intersection graphs of conv...
research
∙
12/18/2019
Dynamic Toolbox for ETRINV
Recently, various natural algorithmic problems have been shown to be ∃R-...
research
∙
12/04/2019
A Framework for Robust Realistic Geometric Computations
We propose a new paradigm for robust geometric computations that complem...
research
∙
08/06/2019
A Universality Theorem for Nested Polytopes
In a nutshell, we show that polynomials and nested polytopes are topolog...
research
∙
07/10/2019
Smoothed Analysis of Order Types
Consider an ordered point set P = (p_1,...,p_n), its order type (denoted...
research
∙
07/02/2019
On the VC-dimension of convex sets and half-spaces
A family S of convex sets in the plane defines a hypergraph H = (S,E) as...
research
∙
03/16/2019
Token Swapping on Trees
The input to the token swapping problem is a graph with vertices v_1, v_...
research
∙
11/03/2018
Smoothed Analysis of the Art Gallery Problem
In the Art Gallery Problem we are given a polygon P⊂ [0,L]^2 on n vertic...
research
∙
02/19/2018
The Complexity of Drawing a Graph in a Polygonal Region
We prove that the following problem is complete for the existential theo...
research
∙
12/14/2017