Date of Award
1-31-2024
Publication Type
Thesis
Degree Name
M.Sc.
Department
Computer Science
Keywords
Art Gallery Problem, City Guarding, Computational Geometry
Supervisor
Ahmad Biniaz
Rights
info:eu-repo/semantics/openAccess
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
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 (half-sphere guards) 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. We then generalize each of the two mentioned problems in some sense with tight bounds. 1. Given a city involving k buildings with any convex-shape base and a total of m top corners, we prove that m − k + 1 cameras of 180◦ field of view (half-sphere guards) are sometimes necessary and always sufficient to guard the ground, walls, roofs, and the sky of the city. 2. Given k simple polygons (convex or non-convex) of total m vertices in the plane which contains r reflex vertices, we prove that m − k − r + 1 cameras of 180◦ field of view are sometimes necessary and always sufficient to guard the free space.
Recommended Citation
Hashemi, Mohammad, "City Guarding with Cameras of Bounded Field of View" (2024). Electronic Theses and Dissertations. 9175.
https://scholar.uwindsor.ca/etd/9175