Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs (Q709066): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.comgeo.2010.07.002 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3102089790 / rank | |||
Normal rank |
Revision as of 21:10, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs |
scientific article |
Statements
Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs (English)
0 references
15 October 2010
0 references
The authors study the problem of monitoring an art gallery modelled as a polygon, the edges of which are arcs of curves, with edge or mobile guards [cf. \textit{O. J'Rouke}, Art gallery theorems and algorithms. The International Series of Monographs on Computer Science, 3. New York-Oxford: Oxford University Press. (1987; Zbl 0653.52001)]. The problem is first transformed to the problem of 2-dominating a constrained triangulation graph. Once a 2-dominating set \(D\) has been found for the constrained triangulation graph, it is proved that either \(D\) is also a guard set for the piecewise-convex polygon or \(D\) is mapped to a mobile guard set for the piecewise-convex polygon. In the case of edge guards, the piecewise-convex polygon is actually monitored by the endpoints of the edges in the guard set. In the case of mobile guards, interior points of edges may also be needed in order to monitor the interior of the polygon (cf. O. J'Rouke, loc. cit.).
0 references
2-dominance edge guards
0 references
mobile guards
0 references
piecewise-convex polygons
0 references
curvilinear art galleries
0 references
triangulation graph
0 references