Maximizing a sum over points with distance constraint in 3D

Question

Problem

The problem statement is as follows, given a set of points in 3D, p_i, and their corresponding energy value, e_i, find a subset of them in which the sum of their energy is maximized, and the distance between each two selected points is greater than a constant r.

What I did so far

These are a summary of my thoughts so far, which I guess are helpful, but may be misleading.

1. A Greedy algorithm: sorting points by their energy value, which isn't guaranteed to give the optimal answer.

2. Generalizing the problem: Graph Model, I created a graph in which each vertex represents a point and two points are connected if and only if they are close enough (their distance is less than r). The goal is now to select an independent set that maximizes the energy function. The problem is now NP-hard (Independent set problem reduces to this, set e_is to 1), which means, if I don't use the spatial properties of the points and assume that space metric is a completely arbitrary function, then the problem is not solvable.

3. Knowing that, I tried to solve the 1D case, in which points lay on a line, AND I DID IT. After sorting points by their x value, let dp[i][j] represent the answer to the problem when we only use the first ith of the points while committing to an extra constraint: distance between each of x_ks (k < i) and x_j must be less than r. This means that we want to solve the problem for the first i elements while still having the possibility of selecting x_j afterward. A dynamic programming algorithm can be constructed from this formulation.

I found the difference between 3. and 2. is that, when we sort the points, if for example p_1 and p_2 don't have a conflict then p_1 and p_i, i > 2 don't conflict at all (by conflicting I mean being closer than r). precisely: in the sorted array for each i, j, k; i < j < k we have p_i < p_j < p_k, therefore p_j - p_i > r results p_k - p_i > r. I think this is what makes the difference and reduces the complexity from NP-Hard to O(n^2)

I was trying to generalize my answer to the 2D case but I got stuck, firstly I tried to sort points by their distance from the original, which doesn't satisfy the property mentioned above, then I tried sorting by their radial angle, again found out I'm not smart enough.

I don't know much about computational geometry, but I feel the answer lies behind some of the techniques used there.

Where did this come from

This is a subproblem of a vision task, to avoid any XY problem, I will explain the original question too, even though I might be complicating this particular subproblem, I found it interesting and will appreciate any help.

The original problem: Assume I have a video of an object sitting on a known marker pattern (ArUco Board) using which I can find camera transformation. I want to compute a point cloud from the surface of the object. I can use each frame and calculate matrix F and then match the image to other images, but firstly, the time complexity is annoying, secondly, most of the frames are very close to each other and we know that low parallax causes higher error. Finally, some images are blurry due to motion.

So I thought, I may compute the reprojection error of the markers as a factor indicating how good a frame is, and set a minimum distance between frames that are selected for matching and surface extraction.

Answer 1

Here is a Mixed-Integer Programming Model for this problem:

With 100 2d points, random locations, random energy levels, mindist=50, I get:

----     42 VARIABLE x.L  selected points

point7  1,    point15 1,    point22 1,    point50 1,    point89 1

This took 0 seconds to optimize (using a good MIP solver).

For 100 3d points, the solution was:

----     42 VARIABLE x.L  selected points

point1  1,    point5  1,    point20 1,    point34 1,    point41 1,    point58 1,    point63 1,    point67 1,    point79 1
point98 1

Also took 0 seconds. Increasing the 3d problem size to 1000 points: 4 seconds.

It is a misconception that a given NP Hard problem, with a given data set, must take lot of time to solve as a MIP.