Johannes Hagauer and Günter Rote:
Three-clustering of points in the plane
1. Extended abstract in: "Algorithms - ESA '93", Proc. First Annual
European Symposium on Algorithms, Bad Honnef, Germany, September 30 - October
2, 1993. Editor: Thomas Lengauer. Lecture Notes in Computer Science 726,
Springer-Verlag, 1993, pp. 192-199.
2. Computational Geometry, Theory and Applications 8 (1997), pp.
Given n points in the plane, we partition them into three classes
such that the maximum distance between two points in the same class is
minimized. The algorithm takes O(n2 log2n)