A Recursive Algorithm for Routing amid Convex Polygonal Obstacles

Abstract

Given a polygonal domain $\mathcal{P}$ comprising $h$ pairwise disjoint convex polygonal obstacles in the plane, together defined with $n$ vertices, this paper presents an algorithm to preprocess $\mathcal{P}$ to compute routing tables at the vertices of $\mathcal{P}$ so that a data packet from any vertex of $\mathcal{P}$ is routed to any other vertex belonging to $\mathcal{P}$. At every vertex $v$ of $\mathcal{P}$ along the routing path, until the packet reaches its destination, the next hop is determined using the routing tables at $v$ and the information stored in the packet header. In $O(n^2(\lg n))$ time, our preprocessing algorithm assigns a unique label of size $O(\sqrt{h}(\lg h)\lg n)$ to each vertex of $\mathcal{P}$ and computes routing tables of size $O(h\lg n+\sqrt{h}(\lg h)(\min ((\frac{1}{\epsilon }{)}^{O(\lg \alpha )},n))$ $\lg n)$ at each vertex of $\mathcal{P}$. The routing path output has a $(7+\epsilon )(\lg h)$ multiplicative stretch. Here, $\epsilon >0$ is an input parameter and $\alpha >1$ is a geometric parameter.