Non-orthogonal ray guarding
No Thumbnail Available
Authors
Sanders, I
Issue Date
1998
Type
Article
Language
en
Keywords
Alternative Title
Abstract
In an earlier paper the notion of a ray guard --'- a guard that can only see along a single ray, was introduced. The ray guarding problem is in siting the fewest possible such guards so that they guard all adjacencies (shared edges or parts of edges) in an orthogonal arrangement of adjacent non-overlapping rectangles. In the earlier paper the problem was restricted by requiring that the direction of sight be parallel to one of the Cartesian axes. This problem was shown to be NP-Complete by a transformation from the vertex cover problem for planar graphs. This paper discusses the more general problem where the rays are not restricted to being orthogonal, the same ray can thus cut both horizontal and vertical adjacencies between adjacent rectangles. The problem is shown to be NP-Complete by a transformation from planar vertex cover. The problem of siting ray guards to cover the adjacencies between adjacent convex polygons is a more general case of the non-orthogonal ray guarding problem and the NP-Completeness proof can be extended to this problem as well. Current work is on developing heuristic algorithms for non-orthogonal ray guarding of adjacent rectangles and for the non-orthogonal ray guarding of convex polygons.
Description
Citation
Sanders, I. (1998) Non-orthogonal ray guarding. Proceedings of the annual research and development symposium, SAICSIT (South African Institute for Computer Scientists and Information Technologists), Van Riebeeck Hotel, Gordons Bay, Cape Town, 23-24 November 1998,