7 papers
Fast Thick-Thin Decomposition for Sparse Spanners on Hyperbolic Surfaces
Sándor Kisfaludi-Bak, Geert van Wordragen
We consider spanners for point sets lying in the hyperbolic plane or on a closed hyperbolic surface with the restriction that spanner edges are not allowed to cross. This is a natu…
Gap-ETH-Tight Algorithms for Hyperbolic TSP and Steiner Tree
Sándor Kisfaludi-Bak, Saeed Odak, Satyam Singh +1
We give an approximation scheme for the TSP in -dimensional hyperbolic space that has optimal dependence on under Gap-ETH. For any fixed dimension and fo…
Improved Bounds for Discrete Voronoi Games
Mark de Berg, Geert van Wordragen
In the planar one-round discrete Voronoi game, two players and compete over a set of voters represented by points in . First, $\ma…
Fine-Grained Complexity of Earth Mover's Distance under Translation
Karl Bringmann, Frank Staals, Karol WÄgrzycki +1
The Earth Mover's Distance is a popular similarity measure in several branches of computer science. It measures the minimum total edge length of a perfect matching between two poin…
Shortest Paths, Convexity, and Treewidth in Regular Hyperbolic Tilings
Sándor Kisfaludi-Bak, Tze-Yang Poon, Geert van Wordragen
Hyperbolic tilings are natural infinite planar graphs where each vertex has degree and each face has edges for some . We study the structure of sho…
Near-Optimal Dynamic Steiner Spanners for Constant-Curvature Spaces
Sándor Kisfaludi-Bak, Geert van Wordragen
We consider Steiner spanners in Euclidean and non-Euclidean geometries. In the Euclidean setting, a recent line of work initiated by Le and Solomon [FOCS'19] and further improved b…