Tillmann Miltzow | DeepAI

AI Chat

Featured Co-authors

Édouard Bonnet
45 publications
Paweł Rzążewski
43 publications
Maarten Löffler
42 publications
Debajyoti Mondal
32 publications
Irina Kostitsyna
28 publications
Anna Lubiw
24 publications
Ahmad Biniaz
23 publications
Patrick Schnider
22 publications
Linda Kleist
19 publications
Mikkel Abrahamsen
19 publications
Fabian Klute
17 publications

∙ 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...

0 Sarita de Berg, et al. ∙

∙ 02/27/2023

The Complexity of Recognizing Geometric Hypergraphs

As set systems, hypergraphs are omnipresent and have various representat...

0 Daniel Bertschinger, et al. ∙

∙ 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...

0 Eunjung Kim, et al. ∙

∙ 12/02/2022

Sometimes Two Irrational Guards are Needed

In the art gallery problem, we are given a closed polygon P, with ration...

0 Lucas Meijer, et al. ∙

∙ 08/13/2022

Avoider-Enforcer Game is NP-hard

In an Avoider-Enforcer game, we are given a hypergraph. Avoider and Enfo...

0 Tillmann Miltzow, et al. ∙

∙ 04/04/2022

Training Fully Connected Neural Networks is ∃ℝ-Complete

We consider the algorithmic problem of finding the optimal weights and b...

0 Daniel Bertschinger, et al. ∙

∙ 12/08/2021

The Complexity of the Hausdorff Distance

We investigate the computational complexity of computing the Hausdorff d...

0 Paul Jungeblut, et al. ∙

∙ 08/09/2021

Topological Art in Simple Galleries

Let P be a simple polygon, then the art gallery problem is looking for a...

0 Daniel Bertschinger, et al. ∙

∙ 08/05/2021

Geometric Embeddability of Complexes is ∃ℝ-complete

We show that the decision problem of determining whether a given (abstra...

0 Mikkel Abrahamsen, et al. ∙

∙ 06/04/2021

On Classifying Continuous Constraint Satisfaction problems

A continuous constraint satisfaction problem (CCSP) is a constraint sati...

0 Tillmann Miltzow, et al. ∙

∙ 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...

0 Mikkel Abrahamsen, et al. ∙

∙ 02/19/2021

Training Neural Networks is ER-complete

Given a neural network, training data, and a threshold, it was known tha...

0 Mikkel Abrahamsen, et al. ∙

∙ 01/19/2021

Local Complexity of Polygons

Many problems in Discrete and Computational Geometry deal with simple po...

0 Fabian Klute, et al. ∙

∙ 09/30/2020

Between Shapes, Using the Hausdorff Distance

Given two shapes A and B in the plane with Hausdorff distance 1, is ther...

0 Marc van Kreveld, et al. ∙

∙ 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...

0 Simon Hengeveld, et al. ∙

∙ 04/16/2020

Framework for ∃ℝ-Completeness of Two-Dimensional Packing Problems

We show that many natural two-dimensional packing problems are algorithm...

0 Mikkel Abrahamsen, et al. ∙

∙ 03/05/2020

Maximum Clique in Disk-Like Intersection Graphs

We study the complexity of Maximum Clique in intersection graphs of conv...

0 Édouard Bonnet, et al. ∙

∙ 12/18/2019

Dynamic Toolbox for ETRINV

Recently, various natural algorithmic problems have been shown to be ∃R-...

0 Mikkel Abrahamsen, et al. ∙

∙ 12/04/2019

A Framework for Robust Realistic Geometric Computations

We propose a new paradigm for robust geometric computations that complem...

0 Jeff Erickson, et al. ∙

∙ 08/06/2019

A Universality Theorem for Nested Polytopes

In a nutshell, we show that polynomials and nested polytopes are topolog...

0 Michael G. Dobbins, et al. ∙

∙ 07/10/2019

Smoothed Analysis of Order Types

Consider an ordered point set P = (p_1,...,p_n), its order type (denoted...

0 Ivor van der Hoog, et al. ∙

∙ 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...

0 Nicolas Grelier, et al. ∙

∙ 03/16/2019

Token Swapping on Trees

The input to the token swapping problem is a graph with vertices v_1, v_...

0 Ahmad Biniaz, et al. ∙

∙ 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...

0 Michael Gene Dobbins, et al. ∙

∙ 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...

0 Anna Lubiw, et al. ∙

∙ 12/14/2017

∀∃R-completeness and area-universality

In the study of geometric problems, the complexity class ∃R turned out t...

0 Michael G. Dobbins, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world