I am trying to solve a triangulation problem, but I am not really sure what is the best way to tackle it.
I have a series of points $P$ in an $n$-dimensional space. These points are clustered in $k$ clusters $P_1, P_2, ..., P_k$ and then projected onto a 2-dimensional space.
I would now like to triangulate this plane with $k$ triangles, maximizing the number of points of the same cluster falling into the same triangle.
An easy example would be:
In this case the points are well-clustered in the 2-dimensional space, but this may or may not be the case.
Any thoughts?