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

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademic

Samenvatting

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.
Originele taal-2Engels
TitelAbstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)
RedacteurenJ. Vahrenhold
Plaats van productieDortmund
UitgeverijTechnische Universität Dortmund
Pagina's121-124
StatusGepubliceerd - 2010
Evenement26th European Workshop on Computational Geometry (EuroCG 2010) - Dortmund
Duur: 22 mrt 201024 mrt 2010
Congresnummer: 26
http://eurocg.org/

Workshop

Workshop26th European Workshop on Computational Geometry (EuroCG 2010)
Verkorte titelEuroCG 2010
StadDortmund
Periode22/03/1024/03/10
Ander26th European Workshop on Computational Geometry (EuroCG 2010)
Internet adres

Vingerafdruk

Duik in de onderzoeksthema's van 'Hide-and-seek: a linear time algorithm for polygon walk problems'. Samen vormen ze een unieke vingerafdruk.

Citeer dit