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.

Ämnesord

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)

Nyckelord

Computational Geometry

Art Gallery Problems

Watchman Routes

Publikations- och innehållstyp

ref (ämneskategori)

kon (ämneskategori)