15 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…
Shifting is Optimal under Gap-ETH: A Lower Bound Framework for Geometric Approximation Schemes
Manuel Cáceres, Sándor Kisfaludi-Bak, Saeed Odak
The shifting technique of Hochbaum and Maass [J.ACM'85] produces PTASes with the fastest known running times for several -dimensional geometric prob…
Touring a Sequence of Orthogonal Polygons
Katrin Casel, Sándor Kisfaludi-Bak, Linda Kleist +3
We study the problem of computing a shortest tour that visits a sequence of polygons with a total number of vertices. A tour is an oriented curve such that…
Charting the Diameter Computation Landscape on Intersection Graphs in the Plane
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Computing the diameter of the intersection graphs of objects is a basic problem in computational geometry. Previous works showed that the complexity of computing the diameter mainl…
Approximation Schemes for Subset TSP and Steiner Tree on Geometric Intersection Graphs
Sándor Kisfaludi-Bak, Dániel Marx
We give approximation schemes for Subset TSP and Steiner Tree on unit disk graphs, and more generally, on intersection graphs of similarly sized connected fat (not necessarily conv…
Charting the Diameter Computation Landscape of Geometric Intersection Graphs in Three Dimensions and Higher
Timothy M. Chan, Hsien-Chih Chang, Jie Gao +3
Recent research on computing the diameter of geometric intersection graphs has made significant strides, primarily focusing on the 2D case where truly subquadratic-time algorithms…