11 citations · 35 across the 18 of their papers we have counts for
18 papers · 1 filter
Polynomial-time algorithm for exact -center problem under continuous Fréchet distance
Soumya Bhattacharya, Serene Rasheed, Sasanka Roy
In this paper, we explore the -center problem for polygonal curves under continuous Fréchet distance. The -center problem, in general, is known to be NP-hard. Aron…
Witness Set in Monotone Polygons: Exact and Approximate
Udvas Das, Binayak Dutta, Satyabrata Jana +2
Given a simple polygon , two points and within are {\em visible} to each other if the line segment between and is contained in $\mathscr{…
Constant Delay Lattice Train Schedules
Jean-Lou De Carufel, Darryl Hill, Anil Maheshwari +2
The following geometric vehicle scheduling problem has been considered: given continuous curves , find non-negative delays $…
Corrigendum to: "Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares", Theoretical Computer Science 769 (2019) 63--74
Sanjib Sadhu, Xiaozhou He, Sasanka Roy +2
In the paper "Linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares", TCS Volume 769 (2019), pages 63--74, the LHIT problem is propos…
Linear Size Planar Manhattan Network for Convex Point Sets
Satyabrata Jana, Anil Maheshwari, Sasanka Roy
Let be an edge-weighted geometric graph such that every edge is horizontal or vertical. The weight of an edge is its length. Let denote the len…
A linear time algorithm to cover and hit a set of line segments optimally by two axis-parallel squares
Sanjib Sadhu, Sasanka Roy, Subhas C. Nandy +1
This paper discusses the problem of covering and hitting a set of line segments in by a pair of axis-parallel squares such that the side length of the larg…
Faster Approximation for Maximum Independent Set on Unit Disk Graph
Subhas C. Nandy, Supantha Pandit, Sasanka Roy
Maximum independent set from a given set of unit disks intersecting a horizontal line can be solved in time and space. As a corollary, we design a factor 2 ap…
Color Spanning Annulus: Square, Rectangle and Equilateral Triangle
Ankush Acharyya, Subhas C. Nandy, Sasanka Roy
In this paper, we study different variations of minimum width color-spanning annulus problem among a set of points in , where each point is ass…
Covering segments with unit squares
Ankush Acharyya, Subhas C. Nandy, Supantha Pandit +1
We study several variations of line segment covering problem with axis-parallel unit squares in . A set of line segments is given. The objective is to find the mi…
Problems on One Way Road Networks
Jammigumpula Ajaykumar, Avinandan Das, Navaneeta Saikia +1
Let be a One Way Road Network where and are the sets of directed horizontal and vertical roads respectively. can be c…
Approximation algorithms for the two-center problem of convex polygon
Sanjib Sadhu, Sasanka Roy, Soumen Nandi +2
Given a convex polygon with vertices, the two-center problem is to find two congruent closed disks of minimum radius such that they completely cover . We propose an algo…
Helly-Type Theorems in Property Testing
Sourav Chakraborty, Rameshwar Pratap, Sasanka Roy +1
Helly's theorem is a fundamental result in discrete geometry, describing the ways in which convex sets intersect with each other. If is a set of points in , we say tha…
Convex Hull and Linear Programming in Read-only Setup with Limited Work-space
Minati De, Subhas C. Nandy, Sasanka Roy
Prune-and-search is an important paradigm for solving many important geometric problems. We show that the general prune-and-search technique can be implemented where the objects ar…
Greedy is good: An experimental study on minimum clique cover and maximum independent set problems for randomly generated rectangles
Ritankar Mandal, Anirban Ghosh, Sasanka Roy +1
Given a set of randomly positioned axis parallel rectangles in 2D, the problem of computing the minimum clique cover (MCC) and maximum independe…
Localized Geometric Query Problems
John Augustine, Sandip Das, Anil Maheshwari +3
A new class of geometric query problems are studied in this paper. We are required to preprocess a set of geometric objects in the plane, so that for any arbitrary query point…
Querying for the Largest Empty Geometric Object in a Desired Location
John Augustine, Sandip Das, Anil Maheshwari +3
We study new types of geometric query problems defined as follows: given a geometric set , preprocess it such that given a query point , the location of the largest circle th…
Largest Empty Circle Centered on a Query Line
John Augustine, Brian Putnam, Sasanka Roy
The Largest Empty Circle problem seeks the largest circle centered within the convex hull of a set of points in and devoid of points from . In this paper,…
Approximation Algorithms for Shortest Descending Paths in Terrains
Mustaq Ahmed, Sandip Das, Sachin Lodha +3
A path from s to t on a polyhedral terrain is descending if the height of a point p never increases while we move p along the path from s to t. No efficient algorithm is known to f…