论文标题
用孔保护多边形
Guarding Polygons with Holes
论文作者
论文摘要
我们研究在移动多代理设置中带有孔的多边形的合作保护问题。鉴于一组代理商，最初在具有$ n $顶点和$ h $ holes的多边形的某个点部署，我们要求代理商以这样的方式进行协作探索和定位自己，以使多边形中的每个点至少可见一个代理，并且一组代理可以明显连接。我们研究了两个计算模型下的问题，其中一个代理可以在其可见性中计算两个点之间的精确距离和角度，而代理只能比较距离和角度。在更强的模型中，我们提供确定性的$ O（n）$圆形算法来计算这种合作的防护设置，同时不需要超过$ \ frac {n + h} {2} $ adents和$ o（\ log n）$ o（\ log n）$ ot otistent memory ersistent memory aent。在较弱的模型中，我们提供了$ O（n^4）$ rough算法，不需要$ \ frac {n+2h} {2} $代理。
We study the Cooperative Guarding problem for polygons with holes in a mobile multi-agents setting. Given a set of agents, initially deployed at a point in a polygon with $n$ vertices and $h$ holes, we require the agents to collaboratively explore and position themselves in such a way that every point in the polygon is visible to at least one agent and that the set of agents are visibly connected. We study the problem under two models of computation, one in which the agents can compute exact distances and angles between two points in its visibility, and one in which agents can only compare distances and angles. In the stronger model, we provide a deterministic $O(n)$ round algorithm to compute such a cooperative guard set while not requiring more than $\frac{n + h}{2}$ agents and $O(\log n)$ bits of persistent memory per agent. In the weaker model, we provide an $O(n^4)$ round algorithm, that does not require more than $\frac{n+2h}{2}$ agents.
