Wednesday, September 27, 2023 - 14:00
The School of Computer Science is pleased to present…
MSc Thesis Proposal Announcement
City Guarding with Cameras of Bounded Field of View
MSc Thesis Proposal by: Mohammad Hashemi
Date: Wednesday, September 27th, 2023
Time: 02:00 PM – 04:00 PM
Location: Essex Hall, Room #122
Abstract:
We study two problems related to the city guarding and the art gallery problems.
1. Given a city with k rectangular buildings, we prove that 3k+1 cameras of 180◦ field of view are always sufficient to guard the free space (the ground, walls, roofs, and the sky). This answers a conjecture of Daescu and Malik (CCCG, 2020).
2. Given k orthogonally convex polygons of total m vertices in the plane, we prove that (m/2)+k+1 cameras of 180◦ field of view are always sufficient to guard the free space (avoiding all the polygons). This answers another conjecture of Daescu and Malik
(Theoretical Computer Science, 2021).
Both upper bounds are tight in the sense that there are input instances that require these many cameras. Our proofs are constructive and suggest simple polynomial-time algorithms for placing these many cameras.
Keywords: Art Gallery Problem, City Guarding, Computational Geometry