Interconnecting Highways
Ding‐Zhu Du, Frank K. Hwang, Guoliang Xue · SIAM Journal on Discrete Mathematics · 1999
We present the problem of constructing roads of minimum total length to interconnect n highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a set of optimality conditions for the problem and show how to construct a solution to meet this set of optimality conditions.