Guarding Polygons With Mutually Visible π-Guards

We study a variant of the classic art gallery problem focusing on mutually visible π-guards. In this variation, for a given polygon P, we aim to place the minimum number of guards of 180° field of view at vertices such that they guard P, and for each guard g there is a guard g' such that g and g' are mutually visible. We define g(n) to represent the minimum number of such guards that are required for any simple polygon with n vertices. Our research focuses on the combinatorial bounds, proving that ²ⁿ−²/₃ ≤ g(n) ≤ ⁴ⁿ/₅ for simple polygons. As for orthogonal polygons, we define ḡ(n) analogously and prove that ³ⁿ−⁴/₇ ≤ ḡ(n) ≤ ⁿ/₂. These lower bounds are existential, as we construct specific polygon families requiring the stated number of guards. Our methodology involves geometric analysis, including polygon partitioning. For simple polygons, we provide an inductive approach to decompose the initial polygon into smaller polygons of fixed sizes, serving as base cases of induction. In the case of orthogonal polygons, we use their structural properties, particularly the dual tree of a convex quadrangulation, to partition the polygon into smaller parts, then guard each part separately.

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Windsor

Year dc:date.issued

2025

Author dc:creator

• Nakhaeisharif, Ali

Advisor dc:contributor.advisor

• Biniaz, Ahmad

Contributors dc:contributor

• scholarship@uwindsor.ca

Statement dc:rights

• info:eu-repo/semantics/openAccess

Handle dc:identifier.uri

https://hdl.handle.net/20.500.14776/12259

OAI identifier oai:identifier

oai:uwindsor.scholaris.ca:20.500.14776/12259