Name
Abstract | ||
|---|---|---|
A T k -guard G in a rectilinear polygon P is a tree of diameter k completely contained in P . The guard G is said to cover a point x if x is visible from some point contained in G . We investigate the function r ( n , h , k ), which is the largest number of T k -guards necessary to cover any rectilinear polygon with h holes and n vertices. The aim of this paper is to prove new lower and upper bounds on parts of this function. In particular, we show the following upper bounds: 1. r(n,0,k)⩽ n k+4 , with equality for even k . 2. r(n,h,1)= n+ 4h 3 + 4 3 4+ 4 3 3. (n,h,2)⩾ n 6 These bounds, along with other lower bounds that we establish, suggest that the presence of holes reduces the number of guards required, if k > 1. In the course of proving the upper bounds, new results on partitioning are obtained which also have efficient algorithmic versions. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1016/0925-7721(96)00014-4 | Computational Geometry: Theory and Applications |
Keywords | DocType | Volume |
rectilinear polygons,rectilinear polygon,visibility,polygon decomposition | Conference | 6 |
Issue | ISSN | Citations |
1 | Computational Geometry: Theory and Applications | 8 |
PageRank | References | Authors |
1.06 | 5 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ervin Györi | 1 | 88 | 21.62 |
| F. Hoffmann | 2 | 460 | 17.87 |
| Klaus Kriegel | 3 | 242 | 26.37 |
| Thomas Shermer | 4 | 89 | 12.10 |