Find the point furthest away from n other points

Question

I am trying to create an algorithm for 'fleeing' and would like to first find points which are 'safe'. That is to say, points where they are relatively distant from other points.

This is 2D (not that it matters much) and occurs within a fixed sized circle.

I'm guessing the sum of the squared distances would produce a good starting equation, whereby the highest score is the furthest away.

As for picking the points, I do not think it would be possible to solve for X,Y but approximation is sufficient.

I did some reading and determined that in order to cover the area of a circle, you would need 7 half-sized circles (with centers forming a hex, and a seventh at the center)

I could iterate through these, all of which are within the circle to begin with. As I choose the best scoring sphere, I could continue to divide them into 7 spheres. Of course, excluding any points which fall outside the original circle.

I could then iterate to a desired precision or a desired level.

To expand on the approach, the assumption is that it takes time to arrive at a location and while the location may be safe, the trip in between may not. How should I incorporate the distance in the equation so that I arrive at a good solution.

I suppose I could square the distance to the new point and multiply it by the score, and iterate from there. It would strongly favor a local spot, but I imagine that is a good behavior. It would try to resolve a safe spot close by and then upon re-calculating it could find 'outs' and continue to sneak to safety.

Any thoughts on this, or has this problem been done before? I wasn't able to find this problem specifically when I looked.

EDIT:

I've brought in the C# implementation of Fortune's Algorithm, and also added a few points around my points to create a pseudo circular constraint, as I don't understand the algorithm well enough to adjust it manually.

I realize now that the blue lines create a path between nodes. I can use the length of these and the distance between the surrounding points to compute a path (time to traverse and danger) and weigh that against the safety (the empty circle it is trying to get to) to determine what is the best course of action. By playing with how these interact, I can eliminate most of the work I would have had to do, simply by using the voronoi. Also my spawning algorithm will use this now, to determine the LEC and spawn at that spot.

Answer 1

You can take the convex hull of your set of locations - the vertices of the convex hull will give you the set of "most distant" points. Next, take the centroid of the points you're fleeing from, then determine which vertex of the convex hull is the most distant from the centroid. You may be able to speed this up by, for example, dividing the playing field into quadrants - you only need to test the vertices that are in the furthermost quadrant (e.g., if the centroid is in the positive-x positive-y quadrant, then you only need to check the vertices in the negative-x negative-y quadrant); if the playing field is an irregular shape then this may not be an option.

As an alternative to fleeing to the most distant point, if you have a starting point that you're fleeing from (e.g. the points you're fleeing from are enemies, and the player character is currently at point X which denotes its starting point), then rather than have the player flee to the most distant point you can instead have the player follow the trajectory that most quickly takes them from the centroid of the enemies - draw a ray from the enemies' centroid through the player's location, and that ray gives you the direction that the player should flee.

If the player character is surrounded then both of these algorithms will give nonsense results, but in that case the player character doesn't really have any viable options anyway.