2
$\begingroup$

I have a 3D space where N spheres of identical size, identified by the location of their centers, are continually inserted. When a new sphere is inserted, I have the ability to efficiently query the locations of any other spheres that may intersect with this sphere.

I can also compute the vector two intersecting spheres will need to move along in order to resolve their intersection in the shortest distance. However, I can't simply move the new sphere over along this vector and call it a day, since this may cause new intersections with other spheres that will then need to be resolved.

My question is, upon inserting a new sphere into this space and finding other spheres it intersects with, how can I efficiently compute the change in position of each of the N spheres in the space that will resolve all intersections in the space? An optimal solution should minimize the total distance traveled by the centers, but near-optimal solutions are fine, and in fact preferred if they are significantly more efficient.

The solution must guarantee that no intersections remain in the space. For my purposes, the 3D space is infinite, and two spheres aren't considered intersecting if they are tangent to each other. Any sphere in the space can be moved.

Example scenario: There are four identical spheres aligned horizontally. The middle two intersect, and the minimum distance required to resolve their intersection is 1. If one of the intersecting spheres moves a distance greater than 0.75 away from the other, it will intersect with one of the outer spheres. An optimal solution here would be to move each of the intersecting spheres away from the other by a distance of 0.5, which results in the least overall distance traveled, since no other intersections would have to be resolved subsequently. visualization of scenario

Improve this question
$\endgroup$
5
  • $\begingroup$ Exactly which spheres are allowed to move? Only those touching the original sphere? Any and all spheres? When you refer to "the N spheres", which spheres are those? $\endgroup$ Commented Jul 15, 2022 at 21:46
  • $\begingroup$ Any sphere can be moved, I'll clarify this $\endgroup$ Commented Jul 15, 2022 at 21:50
  • $\begingroup$ I suspect this problem might be hard in the worst case. Are you looking for a practical solution that will often work well enough on typical instances? Are you looking for the theoretical complexity of the problem, i.e., the worst-case running time of an algorithm that works on all possible inputs? What criteria will you use for evaluating possible algorithms? $\endgroup$ Commented Jul 15, 2022 at 21:52
  • $\begingroup$ Cross-posted: cs.stackexchange.com/q/153003/755, math.stackexchange.com/q/4493674/14578, stackoverflow.com/q/72998849/781723. Please do not post the same question on multiple sites. $\endgroup$ Commented Jul 15, 2022 at 23:15
  • $\begingroup$ Two ideas come to mind. The first is to only insert a sphere where it causes no intersections, thus avoiding the mentioned problem. Now if you did insert it and it caused intersection then do the following. For each pair of intersecting spheres, move them apart until they are no longer intersecting. Now repeat this with newly formed intersections. Keep repeating until there are no more intersections. I am not sure if this is guaranteed to settle though. So a physical simulation as proposed by @D.W. is probably the best way to go. $\endgroup$ Commented Jul 16, 2022 at 10:37

1 Answer 1

Reset to default
2
$\begingroup$

A plausible algorithm is to use a physics simulation of the balls: simulate moving that one ball along that vector, and let it bump other balls out of the way (which might in turn cause a cascading reaction, etc.). This probably won't yield an optimal solution but it will be an efficient way to obtain one plausible solution that might often be not too far from optimal.

One way to obtain an optimal solution is to use quadratically constrained quadratic programming. If you model the center of the $i$th ball as $(x_i,y_i,z_i)$, then all of the constraints (e.g., no two balls are overlapping) are quadratic, and the objective function (minimize total distance travelled) is also quadratic, so this is a QCQP instance, and you could try using an off-the-shelf QCQP solver. As a heuristic, you could pick a subset of balls (e.g., those balls that are moved by the physics simulation of the first paragraph), and only allow them to move, and then use QCQP on that subset of balls.

I don't know whether there are better solutions.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you for the ideas. For the concept presented in the first paragraph, would you run the simulation for both the left and right intersecting balls and then take the minimum distance traveled from the two? Also, would this method work for the example scenario in the question? $\endgroup$ Commented Jul 16, 2022 at 2:12
  • $\begingroup$ @anirudhc1229, I think you could move both spheres simultaneously (away from their common center of mass). Probably worth some experiments to find out how well it works on your datasets. Yes, it "works" in that it gives a solution, but not an optimal solution. $\endgroup$ Commented Jul 16, 2022 at 2:19
  • $\begingroup$ Perhaps each rolling ball could keep track of the distance it’s able to roll along its vector before colliding with another ball. Then, if the distances traveled by two balls that were initially intersecting sum to at least the magnitude of the vector, the intersection can be resolved without creating another one $\endgroup$ Commented Jul 16, 2022 at 2:21

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.