The art gallery problem in polyomino corridors

Kaempen, Kieran

Permalink

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

Description

Title

The art gallery problem in polyomino corridors

Author(s)

Kaempen, Kieran

Issue Date

2022-07-18

Director of Research (if dissertation) or Advisor (if thesis)

Erickson, Jeff G

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• computational geometry
• art gallery problem
• polyomino

Abstract

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.

Graduation Semester

2022-08

Type of Resource

Thesis

Copyright and License Information

Copyright 2022 Kieran Kaempen

Owning Collections