Monday, January 8, 2024 - 14:30 to 16:00
The School of Computer Science is pleased to present…
MSc Thesis Defense Announcement
City Guarding with Cameras of Bounded Field of View
MSc Thesis Defense by: Mohammad Hashemi
Date: Monday, January 8th, 2024
Time: 2:30 PM – 4: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
Thesis Committee:
Internal Reader: Dr. Asish Mukhopadhyay
External Reader: Dr. Jill Urbanic
Advisor: Dr. Ahmad Biniaz
Chair: Dr. Yung (Peter) H. Tsin