Guarding disjoint triangles and claws in the plane (Q1873155)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Guarding disjoint triangles and claws in the plane |
scientific article |
Statements
Guarding disjoint triangles and claws in the plane (English)
0 references
19 May 2003
0 references
It is shown that \(\lfloor (5n+2)/4\rfloor\) guards can monitor the boundaries and the free space around \(n\) disjoint triangles in general position in the plane. The analogous result for claws is even more satisfactory: any \(n\) disjoint claws in the plane can be monitored by at most \(\lfloor 3n/2 \rfloor\) guards, but there are sets of \(n\) claws for which \(\lfloor 3n/2 \rfloor -2\) guards are necessary to monitor the free space. The notion of guarding used in this paper is different from Hadwiger's notion of illuminating a convex body [\textit{H. Hadwiger}, Elem. Math. 15, 130-131 (1960)]. The proofs are based upon the maximum matching of appropriate graphs.
0 references
art gallery
0 references
planar graph
0 references
matching
0 references