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

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.