Files in this item



application/pdfui.pdf (124kB)
(no description provided)PDF


Title:A chromatic art gallery problem
Author(s):Erickson, Lawrence; LaValle, Steven M.
Subject(s):computational geometry
art gallery
Abstract:The art gallery problem asks for the smallest number of guards required to see every point of the interior of a polygon $P$. We introduce and study a similar problem called the chromatic art gallery problem. Suppose that two members of a finite point guard set $S \subset 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, $\chi_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 $P_{spi}$, $\chi_G(P_{spi}) \leq 2$, and for any staircase polygon (strictly monotone orthogonal polygon) $P_{sta}$, $\chi_G(P_{sta}) \leq \sqrt{72n} + 15$. We also show that for any positive integer $k$, there exists a polygon $P_k$ with $3k^2 + 2$ vertices such that $\chi_G(P_k) \geq k$.
Issue Date:2010-08-04
Genre:Technical Report
Publication Status:unpublished
Peer Reviewed:not peer reviewed
Rights Information:National Science Foundation grant #0904501, DARPA SToMP grant HR0011-05-1-0008, and MURI/ONR grant N00014-09-1-1052
Date Available in IDEALS:2010-08-04

This item appears in the following Collection(s)

Item Statistics