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

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

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

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

Algorithms

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

Abstract

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 language	English
Title of host publication	Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)
Editors	J. Vahrenhold
Place of Publication	Dortmund
Publisher	Technische Universität Dortmund
Pages	121-124
Publication status	Published - 2010
Event	26th European Workshop on Computational Geometry (EuroCG 2010) - Dortmund Duration: 22 Mar 2010 → 24 Mar 2010 Conference number: 26 http://eurocg.org/

Workshop

Workshop	26th European Workshop on Computational Geometry (EuroCG 2010)
Abbreviated title	EuroCG 2010
City	Dortmund
Period	22/03/10 → 24/03/10
Internet address	http://eurocg.org/

Cite this

@inproceedings{2a73591ebdbd44a593bcfb1ebb74d1e2,

title = "Hide-and-seek: a linear time algorithm for polygon walk problems",

abstract = "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.",

author = "{Cook IV}, A.F. and C. Fan and J. Luo",

year = "2010",

language = "English",

pages = "121--124",

editor = "J. Vahrenhold",

booktitle = "Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)",

publisher = "Technische Universit{\"a}t Dortmund",

note = "26th European Workshop on Computational Geometry (EuroCG 2010), EuroCG 2010 ; Conference date: 22-03-2010 Through 24-03-2010",

url = "http://eurocg.org/",

}

Cook IV, AF, Fan, C & Luo, J 2010, Hide-and-seek: a linear time algorithm for polygon walk problems. in J Vahrenhold (ed.), Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010). Technische Universität Dortmund, Dortmund, pp. 121-124, 26th European Workshop on Computational Geometry (EuroCG 2010), Dortmund, 22/03/10.

Hide-and-seek: a linear time algorithm for polygon walk problems. / Cook IV, A.F.; Fan, C.; Luo, J.
Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010). ed. / J. Vahrenhold. Dortmund: Technische Universität Dortmund, 2010. p. 121-124.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic

TY - GEN

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

AU - Cook IV, A.F.

AU - Fan, C.

AU - Luo, J.

N1 - Conference code: 26

PY - 2010

Y1 - 2010

N2 - 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.

AB - 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.

M3 - Conference contribution

SP - 121

EP - 124

BT - Abstracts 26th European Workshop on Computational Geometry (EuroCG 2010, Dortmund, Germany, March 22-24, 2010)

A2 - Vahrenhold, J.

PB - Technische Universität Dortmund

CY - Dortmund

T2 - 26th European Workshop on Computational Geometry (EuroCG 2010)

Y2 - 22 March 2010 through 24 March 2010

ER -

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

Abstract

Workshop

Fingerprint

Cite this