JavaScript is disabled for your browser. Some features of this site may not work without it.
| dc.contributor.author | Sanders, I
|
|
| dc.contributor.author | Lubinsky, D
|
|
| dc.contributor.author | Sears, M
|
|
| dc.contributor.editor | Venter, L
|
|
| dc.contributor.editor | Lombard, R.R.
|
|
| dc.date.accessioned | 2018-08-17T10:28:12Z | |
| dc.date.available | 2018-08-17T10:28:12Z | |
| dc.date.issued | 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.identifier.uri | http://hdl.handle.net/10500/24680 | |
| 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 |
