Hide-and-seek: a linear time algorithm for polygon walk problems
Atlas F. Cook, Chenglin Fan, Jun Luo · TU/e Research Portal · 2010
Jack and Jill have decided to play hide-and-seek along the boundary of a simple polygon. To start the game, Jack and Jill each choose an arbitrary path on this boundary. After fixing these paths, our goal is to determine whether Jack can control his speed such that he walks along his path from beginning to end without being seen by Jill. We solve this problem with a linear-sized skeleton visibility diagram that implicitly represents visibility between pairs of points on the boundary of the simple polygon. Note that this data structure has applications for any polygon walk problem where one entity wishes to remain hidden throughout a traversal of some path.