10 citations · 33 across the 24 of their papers we have counts for
16 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…
Extraction Theorems With Small Extraction Numbers
Arjun Agarwal, Sayan Bandyapadhyay
In this work, we develop Extraction Theorems for classes of geometric objects with small extraction numbers. These classes include intervals, axis-parallel segments, axis-parallel…
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…
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…
Minimum-Membership Geometric Set Cover, Revisited
Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1
We revisit a natural variant of geometric set cover, called minimum-membership geometric set cover (MMGSC). In this problem, the input consists of a set of points and a set $\m…
Coresets for Clustering in Geometric Intersection Graphs
Sayan Bandyapadhyay, Fedor V. Fomin, Tanmay Inamdar
Designing coresets--small-space sketches of the data preserving cost of the solutions within -approximate factor--is an important research direction in the study of cente…
Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane
Sayan Bandyapadhyay, Anil Maheshwari, Michiel Smid
Given two sets and of points in the plane, of total size , a {many-to-many} matching between and is a set of pairs such that , and for e…
FPT Approximation for Fair Minimum-Load Clustering
Sayan Bandyapadhyay, Fedor V. Fomin, Petr A. Golovach +2
In this paper, we consider the Minimum-Load -Clustering/Facility Location (MLkC) problem where we are given a set of points in a metric space that we have to cluster and…
Geometric Planar Networks on Bichromatic Points
Sayan Bandyapadhyay, Aritra Banik, Sujoy Bhore +1
We study three classical graph problems - Hamiltonian path, minimum spanning tree, and minimum perfect matching on geometric graphs induced by bichromatic (red and blue) points. Th…
Constrained Orthogonal Segment Stabbing
Sayan Bandyapadhyay, Saeed Mehrabi
Let and each be a set of orthogonal line segments in the plane. A line segment \emph{stabs} a line segment if . It is known that t…
Approximating Dominating Set on Intersection Graphs of Rectangles and L-frames
Sayan Bandyapadhyay, Anil Maheshwari, Saeed Mehrabi +1
We consider the Minimum Dominating Set (MDS) problem on the intersection graphs of geometric objects. Even for simple and widely-used geometric objects such as rectangles, no sub-l…
Polynomial Time Algorithms for Bichromatic Problems
Sayan Bandyapadhyay, Aritra Banik
In this article, we consider a collection of geometric problems involving points colored by two colors (red and blue), referred to as bichromatic problems. The motivation behind st…
On Variants of k-means Clustering
Sayan Bandyapadhyay, Kasturi Varadarajan
\textit{Clustering problems} often arise in the fields like data mining, machine learning etc. to group a collection of objects into similar groups with respect to a similarity (or…
Approximate Clustering via Metric Partitioning
Sayan Bandyapadhyay, Kasturi Varadarajan
In this paper we consider two metric covering/clustering problems - \textit{Minimum Cost Covering Problem} (MCC) and -clustering. In the MCC problem, we are given two point sets…
A Constant Factor Approximation for Orthogonal Order Preserving Layout Adjustment
Sayan Bandyapadhyay, Santanu Bhowmick, Kasturi Varadarajan
Given an initial placement of a set of rectangles in the plane, we consider the problem of finding a disjoint placement of the rectangles that minimizes the area of the bounding bo…
Approximation Schemes for Partitioning: Convex Decomposition and Surface Approximation
Sayan Bandyapadhyay, Santanu Bhowmick, Kasturi Varadarajan
We revisit two NP-hard geometric partitioning problems - convex decomposition and surface approximation. Building on recent developments in geometric separators, we present quasi-p…