Minsum m watchmen’s routes in Stiegl polygons

• We present an O(n2 · min{m, n}) time and O(n · min{m, n}) storage algorithm to compute the minsum set of m watchmen routes given their starting points in a Stiegl polygon ― a staircase polygon where the floor solely consists of one horizontal and one vertical edge ― with n vertices.

Subject headings

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

NATURVETENSKAP  -- Matematik -- Geometri (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Geometry (hsv//eng)

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

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

Keyword

Computational Geometry

Art Gallery Problems

Watchman Routes

Publication and Content Type

ref (subject category)

kon (subject category)