{"id":{"repo_id":"windsor","oai_identifier":"oai:uwindsor.scholaris.ca:20.500.14776/12259"},"canonical_url":"https://search.dev.ndltd.org/etd/windsor/oai:uwindsor.scholaris.ca:20.500.14776/12259","repository":{"repo_id":"windsor","name":"University of Windsor","base_url":"https://uwindsor.scholaris.ca/server/oai/request"},"display":{"title":"Guarding Polygons With Mutually Visible π-Guards","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Nakhaeisharif, Ali"],"institution":"University of Windsor","degree_name":null,"degree_level":null,"degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["scholarship@uwindsor.ca"],"advisors":["Biniaz, Ahmad"],"committee_chairs":[],"committee_members":[],"year":2025,"date_issued":"2025-05-16","date_published":"2025-05-16","updated_at":"2026-07-27T22:04:56Z","subjects":[],"languages":[],"rights":["info:eu-repo/semantics/openAccess"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"https://hdl.handle.net/20.500.14776/12259","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["scholarship@uwindsor.ca"]},{"key":"dc:contributor.advisor","label":"Advisor","values":["Biniaz, Ahmad"]},{"key":"dc:creator","label":"Author","values":["Nakhaeisharif, Ali"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2025-08-18 12:53"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2025-05-29 09:35:41","2025-08-18T16:53:49Z"]},{"key":"dc:date.issued","label":"Date","values":["2025-05-16"]},{"key":"dc:type","label":"Dc Type","values":["thesis"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Windsor"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:rights","label":"Dc Rights","values":["info:eu-repo/semantics/openAccess"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://hdl.handle.net/20.500.14776/12259"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:title","label":"Title","values":["Guarding Polygons With Mutually Visible π-Guards"]}]}],"canonical_facts":{"dc:contributor":["scholarship@uwindsor.ca"],"dc:contributor.advisor":["Biniaz, Ahmad"],"dc:creator":["Nakhaeisharif, Ali"],"dc:date.accessioned":["2025-08-18 12:53"],"dc:date.available":["2025-05-29 09:35:41","2025-08-18T16:53:49Z"],"dc:date.issued":["2025-05-16"],"dc:description.abstract":["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."],"dc:identifier.uri":["https://hdl.handle.net/20.500.14776/12259"],"dc:rights":["info:eu-repo/semantics/openAccess"],"dc:title":["Guarding Polygons With Mutually Visible π-Guards"],"dc:type":["thesis"],"thesis:degree_discipline":["Computer Science"],"thesis:institution_name":["University of Windsor"]},"updated_at":"2026-07-27T22:04:56Z"}