Guarding disjoint triangles and claws in the plane (Q1873155): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3258698 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An efficient algorithm for guard placement in polygons with holes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A combinatorial theorem in plane geometry / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Illuminating rectangles and triangles on the plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4028896 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Illumination of convex discs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4038729 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Lower bounds on the cardinality of the maximum matchings of planar graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4225306 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3799261 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4871750 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Illumination in the presence of opaque line segments in the plane / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4547825 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4945523 / rank | |||
Normal rank |
Revision as of 16:35, 5 June 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