In this paper, a geometric shortest path problem in weighted regions is discussed. An arrangement of lines A, a source s, and a target t are given. The objective is to find a weighted shortest path, Πst, from s to t. Existing approximation algorithms for weighted shortest paths work within bounded regions (typically triangulated). To apply these algorithms to unbounded regions, such as arrangements of lines, there is a need to bound the regions. Here, we present a minimal region that contains Πst, called SP-Hull of A. It is a closed polygonal region that only depends on the geometry of the arrangement A and is independent of the weights. It is minimal in the sense that for any arrangement of lines A, it is possible to assign weights to the faces of A and choose s and t such that Πst is arbitrary close to the boundary of SP-Hull of A. We show that SP-Hull can be constructed in O(nlog n) time, where n is the number of lines in the arrangement. As a direct consequence we obtain a shortest path algorithm for weighted arrangements of lines.

Additional Metadata
Conference 25th Canadian Conference on Computational Geometry, CCCG 2013
Citation
Gheibi, A. (Amin), Maheshwari, A, & Sack, J.-R. (2013). Weighted region problem in arrangement of lines. Presented at the 25th Canadian Conference on Computational Geometry, CCCG 2013.