Guarding disjoint triangles and claws in the plane (Q1873155): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:00, 5 March 2024
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