Finding the shortest watchman route in a simple polygon

• We present the first polynomial-time algorithm that finds the shortest route in a simple polygon such that all points of the polygon is visible from some point on the route. This route is sometimes called the shortest watchman route, and it does not allow any restrictions on the route or on the simple polygon. Our algorithm runs in O(n 3) time.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

Dependable Communication and Computation Systems

Kommunikations- och beräkningssystem

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)