The discrete and mixed minimax 2-center problems.

Letting P be a set of n points in the plane, the discrete minimax 2-center problem (D M M 2 C P) is to find two disks centered at { p 1 , p 2 } ∈ P that minimize the maximum of two terms, namely, the Euclidean distance between two centers and the distance of any other point to the closer center. The mixed minimax 2-center problem (M M M 2 C P) is when one of the two centers is not in P. We present algorithms solving the D M M 2 C P and M M M 2 C P. The time complexities of solving the D M M 2 C P and M M M 2 C P are O (n 2 log ⁡ n) and O (n 2 log 2 ⁡ n) respectively. Furthermore, we consider two Steiner minimum sum dipolar spanning tree problems, in which one of the two dipoles is a Steiner point and the dipoles are both Steiner points. These two problems are shown to be solvable in O (n log ⁡ n) and O (n) time respectively. [ABSTRACT FROM AUTHOR]