2026-09-20T21:29:52Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/116262 2023-07-11 col_2142_5131 col_2142_10761 com_2142_5130 com_2142_10755 com_2142_234

Erickson, Jeff G 2022-08 application/pdf en text Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2022-11-15 without embargo terms The student, Kieran Kaempen, accepted the attached license on 2022-07-17 at 19:04. The student, Kieran Kaempen, submitted this Thesis for approval on 2022-07-17 at 19:09. This Thesis was approved for publication on 2022-07-18 at 15:17. DSpace SAF Submission Ingestion Package generated from Vireo submission #18359 on 2022-11-15 at 18:21:23 The art gallery problem in polyomino corridors Kaempen, Kieran 2022-07-18 computational geometry art gallery problem polyomino 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. Thesis eng https://hdl.handle.net/2142/116262 Copyright 2022 Kieran Kaempen M.S. Thesis Computer Science University of Illinois at Urbana-Champaign Computer Science