Guarding disjoint triangles and claws in the plane (Q1873155): Difference between revisions

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.