4 papers
Parameterized Approximation of Rectangle Stabbing
Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4
In the Rectangle Stabbing problem, input is a set of axis-parallel rectangles and a set of axis parallel lines in the plane. The task is to find a minimum siz…
Approximating Convex Hulls via Range Queries
T. Schibler, J. Xue, J. Zhu
Recently, motivated by the rapid increase of the data size in various applications, Monemizadeh [APPROX'23] and Driemel, Monemizadeh, Oh, Staals, and Woodruff [SoCG'25] studied geo…
Approximation and Hardness of Polychromatic TSP
Thomas Schibler, Subhash Suri, Jie Xue
We introduce the Polychromatic Traveling Salesman Problem (PCTSP), where the input is an edge weighted graph whose vertices are partitioned into equal-sized color classes, and…
Embedding Graphs as Euclidean kNN-Graphs
T. Schibler, S. Suri, J. Xue
Let G = (V, E) be a directed graph on n vertices where each vertex has out-degree k. We say that G is kNN-realizable in d-dimensional Euclidean space if there exists a point set P…