The Planar k-Means Problem is NP-Hard.

Meena Mahajan, Prajakta Nimbhorkar, Kasturi R. Varadarajan

Browse the full WALCOM paper archive.