3 papers
cs.CG2026
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…
cs.CG2026
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…
cs.CG2024
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 .…