Institutional Repository

Non-orthogonal ray guarding

Show simple item record Sanders, I
dc.contributor.editor Petkov, D.
dc.contributor.editor Venter, L. 2019-05-14T13:48:27Z 2019-05-14T13:48:27Z 1998
dc.identifier.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, en
dc.identifier.isbn 1-86840-303-3
dc.description.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 pla­nar 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 devel­oping heuristic algorithms for non-orthogonal ray guarding of adjacent rectangles and for the non-orthogonal ray guarding of convex polygons. en
dc.language.iso en en
dc.title Non-orthogonal ray guarding en
dc.type Article en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account