A chromatic art gallery problem

Erickson, Lawrence; LaValle, Steven M.

Permalink

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

Description

Title

A chromatic art gallery problem

Author(s)

• Erickson, Lawrence
• LaValle, Steven M.

Issue Date

2010-08-04

Keyword(s)

• computational geometry
• art gallery
• Robotics

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$.

Type of Resource

text

Language

en

Permalink

http://hdl.handle.net/2142/16637

Copyright and License Information

National Science Foundation grant #0904501, DARPA SToMP grant HR0011-05-1-0008, and MURI/ONR grant N00014-09-1-1052

Owning Collections