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
Language
eng
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.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.
