Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs - Computer Science > Computational GeometryReportar como inadecuado




Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs - Computer Science > Computational Geometry - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We consider the problem of monitoring an art gallery modeled as a polygon,the edges of which are arcs of curves, with edge or mobile guards. Our focus ison piecewise-convex polygons, i.e., polygons that are locally convex, exceptpossibly at the vertices, and their edges are convex arcs. We transform theproblem of monitoring a piecewise-convex polygon to the problem of 2-dominatinga properly defined triangulation graph with edges or diagonals, where2-dominance requires that every triangle in the triangulation graph has atleast two of its vertices in its 2-dominating set. We show that$\lfloor\frac{n+1}{3} floor$ diagonal guards or $\lfloor\frac{2n+1}{5} floor$edge guards are always sufficient and sometimes necessary, in order to2-dominate a triangulation graph. Furthermore, we show how to compute: adiagonal 2-dominating set of size $\lfloor\frac{n+1}{3} floor$ in linear time,an edge 2-dominating set of size $\lfloor\frac{2n+1}{5} floor$ in $On^2$time, and an edge 2-dominating set of size $\lfloor\frac{3n}{7} floor$ in Ontime. Based on the above-mentioned results, we prove that, for piecewise-convexpolygons, we can compute: a mobile guard set of size$\lfloor\frac{n+1}{3} floor$ in $On\log{}n$ time, an edge guard set of size$\lfloor\frac{2n+1}{5} floor$ in $On^2$ time, and an edge guard set of size$\lfloor\frac{3n}{7} floor$ in $On\log{}n$ time. Finally, we show that$\lfloor\frac{n}{3} floor$ mobile or $\lceil\frac{n}{3} ceil$ edge guards aresometimes necessary. When restricting our attention to monotonepiecewise-convex polygons, the bounds mentioned above drop:$\lceil\frac{n+1}{4} ceil$ edge or mobile guards are always sufficient andsometimes necessary; such an edge or mobile guard set, of size at most$\lceil\frac{n+1}{4} ceil$, can be computed in On time.



Autor: Menelaos I. Karavelas

Fuente: https://arxiv.org/







Documentos relacionados