2 citations · 3 across the 9 of their papers we have counts for
7 papers · 1 filter
Approximation Algorithms for the Two-Watchman Route in a Simple Polygon
Bengt J. Nilsson, Eli Packer
The two-watchman route problem is that of computing a pair of closed tours in an environment so that the two tours together see the whole environment and some length measure on the…
Guarding Polyominoes Under -Hop Visibility
Omrit Filtser, Erik Krohn, Bengt J. Nilsson +2
We study the Art Gallery Problem under -hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest p…
APX-Hardness of the Minimum Vision Points Problem
Mayank Chaturvedi, Bengt J. Nilsson
Placing a minimum number of guards on a given watchman route in a polygonal domain is called the {\em minimum vision points problem}. We prove that finding the minimum number of vi…
Opposing Half Guards
Erik Krohn, Bengt J. Nilsson, Christiane Schmidt
We study the art gallery problem for opposing half guards: guards that can either see to their left or to their right only. We present art gallery theorems, show that the location…
-Transmitter Watchman Routes
Bengt J. Nilsson, Christiane Schmidt
We consider the watchman route problem for a -transmitter watchman: standing at point in a polygon , the watchman can see if intersects 's bou…
Shortest Watchman Tours in Simple Polygons under Rotated Monotone Visibility
Bengt J. Nilsson, David Orden, Leonidas Palios +2
We present an time algorithm for computing and maintaining a minimum length shortest watchman tour that sees a simple polygon under monotone visibility in direction , w…
Local Routing in Sparse and Lightweight Geometric Graphs
Vikrant Ashvinkumar, Joachim Gudmundsson, Christos Levcopoulos +2
Online routing in a planar embedded graph is central to a number of fields and has been studied extensively in the literature. For most planar graphs no -competitive online r…