Institutional Repository

Ray guarding configurations of adjacent rectangles

Show simple item record Sanders, I Lubinsky, D Sears, M
dc.contributor.editor Venter, L
dc.contributor.editor Lombard, R.R. 2018-08-17T10:28:12Z 2018-08-17T10:28:12Z 2000
dc.identifier.citation Sanders, I., Lubinsky, D. & Sears, M. (1997) Ray guarding configurations of adjacent rectangles. Proceedings of the 1997 National Research and Development Conference: Towards 2000, South African Institute of Computer Science and Information Technology), Riverside Sun, 13-14 November, 2000, edited by L.M. Venter and R.R. Lombard (PUCHEE, VTC) en
dc.identifier.isbn 1-86822-300-0
dc.description.abstract Guarding and covering problems have great importance in Computational Geometry. In this paper the notion of a ray guard, a guard that can only 'see' along a single ray, is introduced. The problem of siting the fewest possible such guards so that they guard all adjacencies in an orthogonal arrangement of adjacent non-overlapping rectangles is discussed. The problem is further restricted by requiring that the direction of sight be parallel to an axis and that the guards cannot 'see' outside the rectangles. The problem is motivated by applications in architecture and urban planning. This paper shows that the problem is NP-Complete because of the locally indeterminate choice which can be introduced in positioning guards. A heuristic algorithm to produce a non-redundant set of guards is then presented. Given n rectangles, the algorithm runs in O(n2) time and O(n2) space and proves to be a good approximation in a number of test cases. en
dc.language.iso en en
dc.title Ray guarding configurations of adjacent rectangles en

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UnisaIR


My Account