Routing past unions of disjoint linear barriers

Given a disjoint planar set, {Li, = PiQi, i = 1,…, n}, of line segments called barriers, we consider the question of finding a path Γ of minimal length which connects two given points A and B and which does not “cut” any of the barriers. In Section III we show that such a minimal path exists and that it is polygonal with its bend points lying in W = {Pi, Qi: i = 1,…, n}. The problem is thus reduced to finding the shortest path between two points A and B in an approximate network with vertex set V = W ∪ {A, B}. The latter can be solved by a network routing algorithm such as Dantzig's. Section IV presents Algorithms for reducing the size of the network.