Premium
Routing past unions of disjoint linear barriers
Author(s) -
Chein Orin,
Steinberg Leon
Publication year - 1983
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230130307
Subject(s) - combinatorics , disjoint sets , path (computing) , vertex (graph theory) , shortest path problem , line segment , routing (electronic design automation) , section (typography) , mathematics , line (geometry) , set (abstract data type) , planar , longest path problem , computer science , discrete mathematics , topology (electrical circuits) , algorithm , computer network , graph , geometry , computer graphics (images) , programming language , operating system
Given a disjoint planar set, { L i , = P i Q i , 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 = { P i , Q i : 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.