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?

  • 1
    $\begingroup$ Maybe finding a convex hull could help $\endgroup$ – N74 Aug 4 '17 at 20:13
  • $\begingroup$ @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. $\endgroup$ – BattleWalrus Aug 4 '17 at 20:16

I think you want the largest circle with center inside the convex hull that does not contain any of the given points in its interior.

Circles that pass through the given points but contain no other given points in its interior are called Delaunay circles; they are the key to Delaunay diagrams (triangulations in the generic case).

So, the answer to your problem is: find the Delaunay diagram of the given points. Each face determines an empty circle. Take the largest such circle whose center is in the convex hull; this is the same as being in the corresponding Delaunay face.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.