The art gallery problem in polyomino corridors

The classical Art Gallery Problem asks for a the smallest set of points, called guards, inside a given simple polygon P, such that every point in P is visible to at least one guard. This problem is known to be computationally hard, even in restricted cases. We consider a special case of this problem, where the input polygon P consists of a path of axis-aligned unit squares joined along edges; we call such a polygon a polyomino corridor. We show that an optimal guard set of a corridor can be computed in linear time if the corridor satisfies certain additional conditions. We also formulate (but do not prove) a natural structural conjecture; if this conjecture is true, an optimal guard set can be found in any corridor in linear time. Finally, we present several related geometric and combinatorial results.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2022

Author dc:creator

• Kaempen, Kieran

Contributors dc:contributor

• Erickson, Jeff G

• computational geometry
• art gallery problem
• polyomino

Statement dc:rights

• Copyright 2022 Kieran Kaempen

Language dc:language

en, eng

Handle dc:identifier

https://hdl.handle.net/2142/116262

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F116262