A Recursive Algorithm for Routing amid Convex Polygonal Obstacles

Abstract

Given a polygonal domain $\cal P$ comprising $h$ pairwise disjoint convex polygonal obstacles in the plane, together defined with $n$ vertices, this paper presents an algorithm to preprocess $\cal P$ to compute routing tables at the vertices of $\cal P$ so that a data packet from any vertex of $\cal P$ is routed to any other vertex belonging to $\cal P$. At every vertex $v$ of $\cal 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 $\cal 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 $\cal 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.