5 papers · 1 filter
FPTAS for Polygonal Multi-Robot Motion Planning
Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1
We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain with vertices and…
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…
An -Time Approximation Scheme for Geometric Many-to-Many Matching
Sayan Bandyapadhyay, Jie Xue
Geometric matching is an important topic in computational geometry and has been extensively studied over decades. In this paper, we study a geometric-matching problem, known as geo…
Enclosing Points with Geometric Objects
Timothy M. Chan, Qizheng He, Jie Xue
Let be a set of points in and be a set of geometric objects in , where . We study the problem of computing a…
Euclidean Bottleneck Steiner Tree is Fixed-Parameter Tractable
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +2
In the Euclidean Bottleneck Steiner Tree problem, the input consists of a set of points in called terminals and a parameter , and the goal is to compute a Ste…