# Find the point which is furthest away from existing points while remaining within the convex hull

I have a set of x,y coordinates and wish to find a new coordinate pair which is as far away from any point in the initial set, while also being within the convex hull of the original points.

The current process I have to determine the new point is as follows:

1. Generate every possible midpoint between the original coordinate pairs.
2. Compute the distance between the midpoints and every original point.
3. Find the smallest distance calculated in Step 2 for each midpoint.
4. Find the midpoint with the largest distance from Step 3.

If multiple points have the same maximum distance to the nearest original set of points, only one of those points is needed (for my purpose) and can be selected arbitrarily.

Is there a better method for finding these coordinates?

• Maybe finding a convex hull could help – N74 Aug 4 '17 at 20:13
• @N74 Thank you for the suggestion! My vocabulary is fairly deficient, and a convex hull is the type of boundary I wish to implement. I'll reword the question accordingly. – BattleWalrus Aug 4 '17 at 20:16

It takes $\Theta(n \log n)$ time to find the Delaunay diagram. The other steps run in time $O(n)$.