Best way to track maximal distance in a set of points?

Question

Assume that I have a collection of 2 dimensional points, and a way to determine the distance between them. This collection is frequently modified, with additional points being added and existing points being removed. At any given time, I need to know the maximal and minimal distances between the points, that is, the distance between the two points furthest apart, and the distance between the two points closest together. is there a data structure or algorithm that lends itself particularly well to this task? I would prefer not to have to recalculate the entire set of distances each time that the points change.

Answer 1

Theoretically, you can do this efficiently by storing the convex hull of the points you have.

Whenever you add a new point, test to see if it lies in the interior of this polytope or not. If so, the max distance is preserved. If not, then it may have changed.

Similarly, if you delete a point from the interior, the maximum distance (diameter) is preserved, so change nothing. However, if you delete a boundary point, then the convex hull must be recomputed.

If you are in 2 dimensions, then when you add or remove from the boundary, at most two sides of the polygon are affected. These should be easy to compute, depending on how you store the information (a sequence of line segments, for example).

Coding this may be a bit of a pain, but the simplest way is to mark the points on the boundary, and then have a function that tests if a point lies inside the convex hull of the marked points or not.

Answer 2

Rather than using a convex hull (as suggested in another answer) can you use a Delaunay triangulation??

Min distance:

To calculate the minimum distance from a node to any other in the set you should only need to check the immediate neighbours of the node, i.e. the ones connected to it by an edge in the triangulation.

So if a new node is inserted, update the triangulation, find the neighbours of the new node and any other nodes that were "involved" in the update, compute the distances for all nodes in this local "updated" set and check whether a new minimum was found. Similarly, if an existing node is deleted, again update the triangulation and recompute the distances for all nodes "involved".

There are a class of so-called "incremental" algorithms that can be used to build Delaunay triangulations that only require local modifications of the overall triangulation when inserting/deleting new nodes, so this is the type of approach I'd suggest for frequent insertions/deletions.

Max distance:

As suggested in the convex hull style answer, you would only need to recompute the distances between boundary nodes if a new node was added outside of the existing triangulation or if an existing boundary node was deleted.

Hope this helps.