Seminar Announcement
Date: Tuesday, 21 January 2025
Time: 10.45 - 11.45 AM
Venue: Lecture Hall 1
Parsimonious Guarding
Prahlad Narasimhan Kasthurirangan
PhD student at Stony Brook University.
21-01-25

---

Abstract

In the well-known Art Gallery problem, the goal is to minimize the number of guards within a polygon P to collectively see all of P -- i.e., we seek to cover P with the minimum number of star polygons. The "quality'' of a covering here is simply its cardinality. In this work, we first introduce two novel (and natural) quality measures that capture the "fairness'' and "waste'' of a guard cover. Specifically, we consider:

A "fair'' guard set: We study the MinMax Guarding problem, where the goal is to return a guard set G for P to minimize the maximum area seen by a guard g in G. In sharp contrast with Art Gallery where the optimal guard set has size at most n (the number of vertices in P), we show an instance of MinMax Guarding that has a superpolynomial number of guards in any solution. As our main result for this version, we provide a PTAS for the problem. A guard set to minimize "waste'': We study the MinSum Guarding problem, where the goal is to find a guard set G for P that minimizes the sum of the areas of the visibility polygons of the guards. Note that a partition of P has no waste, as its areas sum to area(P). We show that MinSum Guarding is NP-Hard.

In both versions above the region "assigned'' to a guard is its visibility region. It is also interesting to study how to assign a connected region of P to a guard in G that sees it; we will briefly look at this class of problems if time permits.

This talk is based on joint (unpublished) work with Mayank Goswami, Kien Huynh, Joseph Mitchell, Linh Nguyen, and Valentin Polishchuk.