4

Given a set of points p, I would like to find a point within the space b that bounds the region of p that is as far distant as possible from all points within p.

This is in regards to implementing neighbor avoidance in a flocking simulation as per Craig Reynolds' Boids - if this isn't the best way to avoid neighbors I would love suggestions.

EDIT: In other words, I'd like to find an arbitrary point that is as far from the other points in p as possible, while remaining within the bounding box around p.

By bounding box I mean the solution should be a point that has a y-coordinate that is between the upper and lowermost points, and an x coordinate that is between the left and rightmost points.

To put the question more abstractly, I am looking at this algorithm as a way to find a target for an agent that wants to stay within M units of its nearest neighbors while not getting closer than m units of them. The solution returned by this algorithm should return a point that has the largest distance between it and its closest neighbor.

This is in a 2D plane.

javanix
  • 1,270
  • 3
  • 24
  • 40
  • 1
    That is, find the point `p'` inside `b` for which the sum of all squared distances to all other points is minimal? Try least squares? – zerm Nov 29 '11 at 17:04
  • zerm: You have it backwards - he wants to *maximize* the sum of distances. My sense is that minimizing the appropriate dual problem ought to work nicely, if you can set it up. – Phil Miller Nov 29 '11 at 17:14
  • Another solution would be to maximize the nearest-neighbour distance. Could you please specify your problem more concretely, javanix? – thiton Nov 29 '11 at 17:34
  • I'd also expect the energy landscape of the sum of distances function to be very bad for iterative fitting - with maxima close to edges and all. – thiton Nov 29 '11 at 17:35
  • 1
    what exactly do yo mean by bounding box? The convex hull of the points? Is this in a two dimensional plane (since you are talking about area)? You are not very specific. – Thomas Nov 29 '11 at 17:42
  • Does this need to be exact or is a reasonable heuristic (which occasionally will give a local maxima) good enough? – Ron Warholic Nov 29 '11 at 18:45
  • @Novelocrat You are right, of course. I was a bit distracted.. However, maybe you can transform the maximization somehow into a minimization and solve it using some minimizert.. – zerm Nov 29 '11 at 19:06
  • @Ron Warholic A reasonable heuristic would be preferable to the exact solution if it is significantly faster than the alternative. These calculations could be done once per second so the faster the better. – javanix Nov 29 '11 at 19:19

2 Answers2

3

It sounds like the solution must lie on one of the intersections of the Voronoi diagram for the (other) agents. So an algorithmic solution is to construct the Voronoi diagram, iterate the intersections, and pick the one that has greatest shortest distance to a neighbor.

Antti Huima
  • 25,136
  • 3
  • 52
  • 71
1

I think the farthest point should be either on the box boundary or at an equal distance between its two closest points. If it is not, then you should be able to shift it slightly to make it further from the closer of the two points. This puts it on a line of the diagram. One of the directions along that line will move it further from both points, so you could move it until that line joins another at a point. Therefore I would expect it to be either on the boundary, or on one of the intersections of a http://en.wikipedia.org/wiki/Voronoi_diagram. You could check the corners of the boundary, where the lines of the Voronoi diagram intersect the boundary, and the intersections of the Voronoi diagram to find the farthest point. Even if you don't do it this way, you might find the Voronoi diagram useful as a way of finding nearest neighbours for another approach - some variety of branch and bound might work.

mcdowella
  • 19,301
  • 2
  • 19
  • 25