A divide-and-conquer based preprocessing for routing in a simple polygon

期刊论文
发表日期：

2025年9月4日

查看全文

Siddharth Gaur,
R. Inkulu

摘要

Given a simple polygon P defined with n vertices in the plane, we preprocess P and compute routing tables at every vertex of P. In the routing phase, a packet originating at any source vertex of P is routed to its destination vertex belonging to P. At every vertex v of P along the routing path, until the packet reaches its destination, the next hop is determined using the routing tables at v and the additional information (including the packet’s destination vertex label) in the packet. We show our routing scheme constructs routing tables in \(O\big (n \big (1+\frac{1}{\epsilon }\big ) \big (\lg {n}\big )^3\big )\) time and the routing tables at all the vertices of P together use \(O\big (n+\frac{n}{\epsilon }\big (\lg {n}\big )^3\big )\) space. The multiplicative stretch factor of the routing path computed by our algorithm is upper bounded by \((2+\epsilon )\lg {n}\) . Here, \(\epsilon > 0\) is an input parameter.