-
Chapter and Conference Paper
On Half Guarding Polygons
Given a polygon P and a set of potential guard locations \(G \in P\) G ...
-
Chapter and Conference Paper
Guarding Polyominoes Under k-Hop Visibility
We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertice...
-
Chapter and Conference Paper
On Vertex Guarding Staircase Polygons
In this paper, we consider the variant of the art gallery problem where the input polygon is a staircase polygon. Previous works on this problem gave a 2-approximation for point guarding a staircase polygon (w...
-
Chapter and Conference Paper
On the Complexity of Half-Guarding Monotone Polygons
We consider a variant of the art gallery problem where all guards are limited to seeing to the right inside a monotone polygon. We call such guards: half-guards. We provide a polynomial-time approximation for ...
-
Chapter and Conference Paper
A Characterization of Visibility Graphs for Pseudo-polygons
In this paper, we give a characterization of the visibility graphs of pseudo-polygons. We first identify some key combinatorial properties of pseudo-polygons, and we then give a set of five necessary condition...
-
Chapter and Conference Paper
The VC-Dimension of Visibility on the Boundary of a Simple Polygon
In this paper, we prove that the VC-Dimension of visibility on the boundary of a simple polygon is exactly 6. Our result is the first tight bound for any variant of the VC-Dimension problem regarding simple po...
-
Article
Open AccessImproved Approximations for Guarding 1.5-Dimensional Terrains
We present a 4-approximation algorithm for the problem of placing the fewest guards on a 1.5D terrain so that every point of the terrain is seen by at least one guard. This improves on the previous best approx...
-
Article
On Metric Clustering to Minimize the Sum of Radii
Given an n-point metric (P,d) and an integer k>0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n ...
-
Chapter and Conference Paper
An Approximation Scheme for Terrain Guarding
We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. Our algorithm is a local search algorithm inspired by the recent ...
-
Chapter and Conference Paper
On Metric Clustering to Minimize the Sum of Radii
Given an n-point metric (P,d) and an integer k > 0, we consider the problem of covering P by k balls so as to minimize the sum of the radii of the balls. We present a randomized algorithm that runs in n ...
