Find a point that maximizes total distance from a set of points within a bounded area

Question

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.

Answer 1

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.

Answer 2

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.