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. 87-95.


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) time.
  PostScript file (gzippedpdf file TeX .dvi file (gzipped)
other papers about this subject