Given a set of X kd (k-dimensional) points, find the maximum number of closed subsets of these points such that no subsets (each forming a convex hull) overlap or intersect, that each subset is exactly of size N, and that the distance from each vertex to the center of its subset (average center of all points in subset) is maximally D. Furthermore, each vertex may only belong to at most one subset. The solution should be precise, but can be a good approximation if precise is way too expensive. The set of subsets should be calculated, not how many subsets belong to the set.

By overlap, this means that there are no edge, face, etc intersections and that one subset can't have another subset inside of it. If you were to have closed subsets on a 2D cartesian coordinate system, then the closed subsets would form shapes and none of these shapes would be allowed to overlap.

Let it be known that I'm not very proficient with graph theory.

My current methodology is to convert the points into a near triangulation graph. From there, I have no idea where to go. Of course, my entire starting point may be wrong as well.

Idea 1

  • Calculate center point of graph. From the farthest vertices, select N - 1 closest vertices such that their inclusion keeps the set valid and remove them from the graph.

Idea 2

  • Starting from vertices with the fewest reachable vertices (distance <= 2R), create valid subsets using reachable vertices with maximum reachable vertices, or are closest, or have minimum (I've tried all three, and all three failed).

Idea 3

  • Start with triangles that share minimal vertices and expand them, always working off of triangles that have as few vertices as possible (bad things can happen towards the center of the graph, giving an incorrect solution).

There are also problems with near triangulation. What happens if N is 2? It would turn into pairs. I guess the algorithm could have a special case for N = 0, N = 1, and N = 2, and then actually go into a general algorithm for N >= 3.

Another way to think about the problem is that, from a set of points, it is trying to build a maximal list of polygons with N faces. I've been working it from a 2D standpoint, but I also understand that what the problem changes a bit when going to 3D and beyond. For example, a 2D shape in 3D has undefined faces, so how then would the general algorithm make sure that the plane doesn't intersect any other planes or volumes?

Ideally, I'd want this to work for any dimension >= 2. I also may want to draw the 2D/3D stuff down the road. The 4D stuff may be interesting to simulate.

I'm really looking for an optimal solution here. I am starting to think that this problem may be NP-Hard.

This problem is for an ability in a game that I've wanted to do for years.

  • 1
    $\begingroup$ What's a kd point? How are you defining center? What do you mean by "edge/face intersection"? Subsets don't have edges or faces. Are you talking about the convex hulls of each subset? Have you looked at resources on the facility location problem? Are you looking for an exact answer or an approximate answer? If an approximate answer is good enough, have you tried looking at clustering algorithms? $\endgroup$ – D.W. Dec 4 '14 at 1:18
  • $\begingroup$ kd = k-dimensional. Center is the center of the convex hull defined by the subset. The answer should be precise. I'll take a look at the facility location problem. I edited the post to answer these questions as well. Thank you. Don't know if that is the problem though. As many points as possible must be used. Actually, a good approximation will be ok, but really prefer precise. $\endgroup$ – nestharus Dec 4 '14 at 3:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.