Geometric routing
Petr Vojtěchovský, Sadananda Narayanappa · 2006
This thesis is concerned with the problem of optimal routing in geometric graphs. A geometric graph is a graph in which each node has location information, and edges have some geometrical constraints. The problems considered in this thesis fall into two main categories: (i) routing in ad hoc wireless networks, (ii) routing through weighted regions. The fundamental problem in ad hoc wireless networks is broadcasting messages without flooding and it is modeled on unit disk graphs. The Weighted Region Problem deals with finding an optimal route between two points in the plane, and is modeled on a planar graph where paths are allowed to pass through the faces. The main results of this thesis are: (a) an improved approximation result for a unit disk covering problem, (b) an elimination scheme for a minimum forwarding set problem, (c) analysis of two-hop realizable graphs, (d) exact solutions for simple weighted region problems, (e) algorithms to reduce distortions in raster paths, (f) comparison and analysis of vector based algorithms.