It's been ages since I've used K-means, but I thought you had a lot of freedom in how you define your distance function.