In this thesis, we introduce a variant version of the segment center problem : Given two sets P and Q of planar points are ordered with respect to x-coordinates and splitted by a river which consists of two horizontal lines, construct a bridge with an arbitrary direction in such a way that the maximum-length of the path from $p_i ∈ P to $q_j ∈ Q is minimized.
Using a furthest voronoi diagram and a matrix searaching algorithm, we present a linear algorithm which is optimal for constructing a bridge in the $L_2$-metric. We describe a linear algorithm for the same problem in the $L_1$-metric and the $L_∞$-metric when the sets P and Q are not ordered. In addition, we prove that the proposed algorithm can be applied with slight modification to the case in which a bridge must be constructed vertically.
