Insert a point into a finite 2D region with maximum distance to existing points.

Question

I have a set of 2D points inside a finite 2D region of space (let's say a world-aligned rectangle to keep things simple for now). What would be an exceedingly efficient way to insert a new point into the set that has a relatively large distance to its new closest neighbour?

I could slowly build a Delaunay triangulation and limit my search to the largest triangles only, but I was hoping someone has a different (better) idea.

Goodwill, David

---

Edit:

Forgot to mention that I need to do this thousands of times, every time taking all the previous points into account. I'm looking for an algorithm that doesn't slow down to a crawl as my point set grows.

Answer 1

Use the Bowyer-Watson or other incremental algorithm to maintain the Voronoi diagram. The vertexes of the Voronoi diagram are candidate points, keep all the candidate points in a priority queue ordered by distance to the source points. That should be pretty fast, and optimal (at least, optimal at each step).

Were you looking for something faster and less optimal?