{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/42233"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/42233","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"An art gallery approach to ensuring that landmarks are distinguishable","abstract":"How many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class? To study this, we introduce the chromatic art gallery problem. A guard set S ⊂ P is a set of points in a polygon P such that for all p ∈ P, there exists an s ∈ S such that s and p are mutually visible. Suppose that two members of a finite guard set S ⊂ P must be given different colors if their visible regions overlap. What is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon P? We call this number, χG(P), the chromatic guard number of P. We believe this problem has never been examined before, and it has potential applications to robotics, surveillance, sensor networks, and other areas. We show that for any spiral polygon Pspi, χG(Pspi) ≤ 2, and for any staircase polygon (strictly monotone orthogonal polygon) Psta, χG(Psta) ≤ 3. For lower bounds, we construct a polygon with 4k vertices that requires k colors. We also show that for any positive integer k, there exists a monotone polygon Mk with 3k2 vertices such that χG(Mk) ≥ k, and for any odd integer k, there exists an orthogonal polygon Rk with 4k2 + 10k + 10 vertices such that χG(Rk) ≥ k.","abstract_html":"How many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class? To study this, we introduce the chromatic art gallery problem. A guard set S ⊂ P is a set of points in a polygon P such that for all p ∈ P, there exists an s ∈ S such that s and p are mutually visible. Suppose that two members of a finite guard set S ⊂ P must be given different colors if their visible regions overlap. What is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon P? We call this number, χG(P), the chromatic guard number of P. We believe this problem has never been examined before, and it has potential applications to robotics, surveillance, sensor networks, and other areas. We show that for any spiral polygon Pspi, χG(Pspi) ≤ 2, and for any staircase polygon (strictly monotone orthogonal polygon) Psta, χG(Psta) ≤ 3. For lower bounds, we construct a polygon with 4k vertices that requires k colors. We also show that for any positive integer k, there exists a monotone polygon Mk with 3k2 vertices such that χG(Mk) ≥ k, and for any odd integer k, there exists an orthogonal polygon Rk with 4k2 + 10k + 10 vertices such that χG(Rk) ≥ k.","abstract_has_math":false,"creators":["Erickson, Lawrence"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"M.S.","degree_level":"Thesis","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["LaValle, Steven M."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2013,"date_issued":"2013-02-03T19:28:42Z","date_published":"2013-02-03T19:28:42Z","updated_at":"2026-07-22T22:25:33Z","subjects":["Art Gallery","Robotics","Computational Geometry"],"languages":["en"],"rights":["Copyright 2012 Lawrence Erickson"],"rights_urls":[],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/2142/42233","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["LaValle, Steven M."]},{"key":"dc:creator","label":"Author","values":["Erickson, Lawrence"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2013-02-03T19:28:42Z","2012-12"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Thesis"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M.S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Art Gallery","Robotics","Computational Geometry"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["Copyright 2012 Lawrence Erickson"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/42233"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["How many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class? To study this, we introduce the chromatic art gallery problem. A guard set S ⊂ P is a set of points in a polygon P such that for all p ∈ P, there exists an s ∈ S such that s and p are mutually visible. Suppose that two members of a finite guard set S ⊂ P must be given different colors if their visible regions overlap. What is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon P? We call this number, χG(P), the chromatic guard number of P. We believe this problem has never been examined before, and it has potential applications to robotics, surveillance, sensor networks, and other areas. We show that for any spiral polygon Pspi, χG(Pspi) ≤ 2, and for any staircase polygon (strictly monotone orthogonal polygon) Psta, χG(Psta) ≤ 3. For lower bounds, we construct a polygon with 4k vertices that requires k colors. We also show that for any positive integer k, there exists a monotone polygon Mk with 3k2 vertices such that χG(Mk) ≥ k, and for any odd integer k, there exists an orthogonal polygon Rk with 4k2 + 10k + 10 vertices such that χG(Rk) ≥ k.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-12-06T18:45:03Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Erickson_Lawrence.pdf: 179753 bytes, checksum: d34ec8c8f18bdbcfa89b409636ca3918 (MD5)","Made available in DSpace on 2013-02-03T19:28:42Z (GMT). No. of bitstreams: 2 Lawrence_Erickson.pdf: 179753 bytes, checksum: d34ec8c8f18bdbcfa89b409636ca3918 (MD5) license.txt: 4067 bytes, checksum: d803333f8e468a760f9ce6d3a305bf53 (MD5)"]},{"key":"dc:title","label":"Title","values":["An art gallery approach to ensuring that landmarks are distinguishable"]}]}],"canonical_facts":{"dc:contributor":["LaValle, Steven M."],"dc:creator":["Erickson, Lawrence"],"dc:date":["2013-02-03T19:28:42Z","2012-12"],"dc:description":["How many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class? To study this, we introduce the chromatic art gallery problem. A guard set S ⊂ P is a set of points in a polygon P such that for all p ∈ P, there exists an s ∈ S such that s and p are mutually visible. Suppose that two members of a finite guard set S ⊂ P must be given different colors if their visible regions overlap. What is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon P? We call this number, χG(P), the chromatic guard number of P. We believe this problem has never been examined before, and it has potential applications to robotics, surveillance, sensor networks, and other areas. We show that for any spiral polygon Pspi, χG(Pspi) ≤ 2, and for any staircase polygon (strictly monotone orthogonal polygon) Psta, χG(Psta) ≤ 3. For lower bounds, we construct a polygon with 4k vertices that requires k colors. We also show that for any positive integer k, there exists a monotone polygon Mk with 3k2 vertices such that χG(Mk) ≥ k, and for any odd integer k, there exists an orthogonal polygon Rk with 4k2 + 10k + 10 vertices such that χG(Rk) ≥ k.","Item withdrawn by Mark Zulauf (zulauf@illinois.edu) on 2012-12-06T18:45:03Z Item was in collections: University of Illinois Theses & Dissertations (ID: 1) No. of bitstreams: 1 Erickson_Lawrence.pdf: 179753 bytes, checksum: d34ec8c8f18bdbcfa89b409636ca3918 (MD5)","Made available in DSpace on 2013-02-03T19:28:42Z (GMT). No. of bitstreams: 2 Lawrence_Erickson.pdf: 179753 bytes, checksum: d34ec8c8f18bdbcfa89b409636ca3918 (MD5) license.txt: 4067 bytes, checksum: d803333f8e468a760f9ce6d3a305bf53 (MD5)"],"dc:identifier":["http://hdl.handle.net/2142/42233"],"dc:language":["en"],"dc:rights":["Copyright 2012 Lawrence Erickson"],"dc:subject":["Art Gallery","Robotics","Computational Geometry"],"dc:title":["An art gallery approach to ensuring that landmarks are distinguishable"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Thesis"],"thesis:degree_name":["M.S."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:33Z"}