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 (DMM2CP) is to find two disks centered at {p₁,p₂}∈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 (MMM2CP) is when one of the two centers is not in P. We present algorithms solving the DMM2CP and MMM2CP. The time complexities of solving the DMM2CP and MMM2CP are O(n²log⁡n) and O(n²log²⁡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(nlog⁡n) and O(n) time respectively.