An Art Gallery Approach To Ensure That Landmarks Are Distinguishable

Kshitij Gajjar
Friday, 6 Sep 2013, 16:00 to 17:30
D-405 (D-Block Seminar Room)
In a 2-dimensional setting, how many different classes of partially distinguishable landmarks are needed to ensure that a robot can always see a landmark without simultaneously seeing two of the same class? In other words, what is the minimum number of colors required to color any guard set (not necessarily a minimal guard set) of a polygon such that no two guards of the same colors see a common point (conflict-free coloring)? In this talk we will see lower bounds of colors for conflict free guarding of general, monotone and orthogonal  polygons. This is recent work by Lawrence Erickson and Steven LaValle.