research
∙
05/02/2023
A Quadtree for Hyperbolic Space
We propose a data structure in d-dimensional hyperbolic space that can b...
share
research
∙
08/16/2022
Computing Smallest Convex Intersecting Polygons
A polygon C is an intersecting polygon for a set O of objects in the pla...
research
∙
08/11/2022
Subexponential Parameterized Directed Steiner Network Problems on Planar Graphs: a Complete Classification
In the Directed Steiner Network problem, the input is a directed graph G...
research
∙
03/15/2022
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
The Dynamic Time Warping (DTW) distance is a popular measure of similari...
research
∙
03/07/2022
Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs
We initiate the study of diameter computation in geometric intersection ...
research
∙
02/17/2022
Computing list homomorphisms in geometric intersection graphs
A homomorphism from a graph G to a graph H is an edge-preserving mapping...
research
∙
09/20/2021
Clique-Based Separators for Geometric Intersection Graphs
Let F be a set of n objects in the plane and let G(F) be its intersectio...
research
∙
09/09/2021
Online Search for a Hyperplane in High-Dimensional Euclidean Space
We consider the online search problem in which a server starting at the ...
research
∙
11/07/2020
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
We revisit the classic task of finding the shortest tour of n points in ...
research
∙
08/27/2020
On the Approximability of the Traveling Salesman Problem with Line Neighborhoods
We study the variant of the Euclidean Traveling Salesman problem where i...
research
∙
03/22/2020
Euclidean TSP in Narrow Strip
We investigate how the complexity of Euclidean TSP for point sets P insi...
research
∙
02/13/2020
A quasi-polynomial algorithm for well-spaced hyperbolic TSP
We study the traveling salesman problem in the hyperbolic plane of Gauss...
research
∙
09/26/2019
How does object fatness impact the complexity of packing in d dimensions?
Packing is a classical problem where one is given a set of subsets of Eu...
research
∙
02/25/2019
On One-Round Discrete Voronoi Games
Let V be a multiset of n points in R^d, which we call voters, and let k≥...
research
∙
12/10/2018
Hyperbolic intersection graphs and (quasi)-polynomial time
We study unit ball graphs (and, more generally, so-called noisy uniform ...
research
∙
11/16/2018
Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
The Planar Steiner Tree problem is one of the most fundamental NP-comple...
research
∙
07/18/2018
An ETH-Tight Exact Algorithm for Euclidean TSP
We study exact algorithms for Euclidean TSP in R^d. In the early 1990s ...
research
∙
03/28/2018
A Framework for ETH-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
03/28/2018
Framework for ETH-tight Algorithms and Lower Bounds in Geometric Intersection Graphs
We give an algorithmic and lower-bound framework that facilitates the co...
research
∙
09/15/2017