The discrete and mixed minimax 2-center problems
2016
Abstract 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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
21
References
0
Citations
NaN
KQI