[PDF][PDF] Guarding Monotone Polygons with Half-Guards.
We consider a variant of the art gallery problem where all guards are limited to seeing to the
right inside of a monotone polygon. We provide a polynomial-time 4-approximation
algorithm for a version of the problem where we wish to point-guard the vertices of the
polygon. We then extend this algorithm and provide a O (1)-approximation to point-guard the
boundary of the polygon and ultimately the entire polygon.
right inside of a monotone polygon. We provide a polynomial-time 4-approximation
algorithm for a version of the problem where we wish to point-guard the vertices of the
polygon. We then extend this algorithm and provide a O (1)-approximation to point-guard the
boundary of the polygon and ultimately the entire polygon.
Abstract
We consider a variant of the art gallery problem where all guards are limited to seeing to the right inside of a monotone polygon. We provide a polynomial-time 4-approximation algorithm for a version of the problem where we wish to point-guard the vertices of the polygon. We then extend this algorithm and provide a O (1)-approximation to point-guard the boundary of the polygon and ultimately the entire polygon.
2017.cccg.ca
以上显示的是最相近的搜索结果。 查看全部搜索结果