School of Technology and Computer Science Seminars

An Art Gallery Approach To Ensure That Landmarks Are Distinguishable

by Mr. Suneel Sarswat (School of Technology and Computer Science, TIFR)

Friday, September 6, 2013 from to (Asia/Kolkata)
at Colaba Campus ( D-405 (D-Block Seminar Room) )
Description
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.