[comp.theory] Euclidian clustering

fellous@rana.usc.edu (Jean-Marc Fellous) (05/14/91)

I am interested in pattern recognition and learning methods for it.
One of the simplest approaches is to cluster the data. The usual
distance metric is the Euclidean which led me to the following question:

Does there exist a Euclidian clustering problem which is NP-complete?
If yes, where is the proof published?

Thank's for pointers to the literature

***********************
                          JOACHIM BUHMANN
                          University of Southern California
                          Center for Neural Engineering
                          HNB 09, University Park
                          Los Angeles, Ca 90089-0252
                          email: buhmann@rana.usc.edu