Hide-and-seek: a linear time algorithm for polygon walk problems

A.F. Cook IV, C. Fan, J. Luo

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademic


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.
Original languageEnglish
Title of host publicationAbstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)
EditorsJ. Vahrenhold
Place of PublicationDortmund
PublisherTechnische Universität Dortmund
Publication statusPublished - 2010
Event26th European Workshop on Computational Geometry (EuroCG 2010) - Dortmund
Duration: 22 Mar 201024 Mar 2010
Conference number: 26


Workshop26th European Workshop on Computational Geometry (EuroCG 2010)
Abbreviated titleEuroCG 2010
Internet address


Dive into the research topics of 'Hide-and-seek: a linear time algorithm for polygon walk problems'. Together they form a unique fingerprint.

Cite this