Watchman route problem

Watchman route problem

The Watchman Problem is an optimization problem in computational geometry where the objective is to compute the shortest route a watchman should take to guard an entire area with obstacles given only a map of the area. The challenge is to make sure the watchman peeks behind every corner and to determine the best order in which corners should be visited in. There are polynomial-time solutions but they all suffer from severe numerical problems inherent in the computations.

Note that this is not the same as the museum problem, which is about a similar situation, but with multiple, stationary watchmen.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… …   Wikipedia

  • List of combinatorial computational geometry topics — enumerates the topics of computational geometry that states problems in terms of geometric objects as discrete entities and hence the methods of their solution are mostly theories and algorithms of combinatorial character.See List of numerical… …   Wikipedia

  • Visibility (geometry) — Visibility is a mathematical abstraction of the real life notion of visibility.Given a set of obstacles in the Euclidean space, two points in the space are said to be visible to each other, if the line segment that joins them does not intersect… …   Wikipedia

  • Maritime history of California — History of California This article is part of a series Timeline …   Wikipedia

  • HISTORICAL SURVEY: THE STATE AND ITS ANTECEDENTS (1880–2006) — Introduction It took the new Jewish nation about 70 years to emerge as the State of Israel. The immediate stimulus that initiated the modern return to Zion was the disappointment, in the last quarter of the 19th century, of the expectation that… …   Encyclopedia of Judaism

  • National Register of Historic Places listings in Washington County, Utah — Location of Washington County in Utah This is a list of the National Register of Historic Places listings in Washington County, Utah. This is intended to be a complete list of the properties and districts on the National Register of Historic… …   Wikipedia

  • History of radar — The history of radar starts with experiments by Heinrich Hertz in the late 19th century that showed that radio waves were reflected by metallic objects. This possibility was suggested in James Clerk Maxwell s seminal work on electromagnetism.… …   Wikipedia

  • Security guard — Private factory guard Occupation Activity sectors Security Description A security guard (or security officer) is a person who is paid to protect pro …   Wikipedia

  • National Register of Historic Places listings in Zion National Park — This is a list of the National Register of Historic Places listings in Zion National Park. This is intended to be a complete list of the properties and districts on the National Register of Historic Places in Zion National Park, Utah, United… …   Wikipedia

  • River Don, South Yorkshire — River Don The River Don as it flows past Hillsborough Stadium. Origin Pennines …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”