4 papers
Witness Set in Weak Visibility Polygons is Polynomial-Time Solvable
Udvas Das, Shouvik Mondal, Sasanka Roy
In the classical Art Gallery Problem (AGP), guards are placed in a polygon so that together they see every point. The Witness Set Problem (WSP), introduced by Amit, Mitchell, and P…
Perfectly Guarding Straits: Exact Algorithms for Weak Visibility Polygons
Shouvik Mondal, Udvas Das, Sasanka Roy
The Art Gallery Problem (AGP) asks for the fewest guards that see all of a simple polygon. It is -complete, hence NP-hard. We show that for a particular class of…
Witness Set: A Visibility Problem in
Satyabrata Jana, Debabrata Pal, Bodhayan Roy +1
We study the Witness Set problem, a natural dual to the classical Art Gallery problem. In the Witness Set problem, we are given a polygon and an integer as input, and the o…
New Complexity and Algorithmic Bounds for Minimum Consistent Subsets
Aritra Banik, Sayani Das, Anil Maheshwari +6
In the Minimum Consistent Subset (MCS) problem, we are presented with a connected simple undirected graph , consisting of a vertex set of size and an edge set .…