Utrecht University ∗

The Weighted Region Problem is defined as the problem of find-ing a cost-optimal path in a weighted planar polygonal subdivision. Searching for paths on a grid representation of the scene is fast and easy to implement. However, grid representations do not capture the exact geometry of the scene. Hence, grid paths can be inaccu-rate or might not even exist at all. Methods that work on an exact representation of the scene can approximate an optimal path up to an arbitrarily small -error. However, these methods are computa-tionally inefficient and thus not well-suited for real-time applica-tions. In this paper, we analyze the quality of optimal paths on a 8-neighbor-grid. We prove that the costs of such a path in a scene with weighted regions can be arbitrarily high in the general case. If all regions are aligned with the grid, we prove that the costs are at mos