In computational geometry, the diameter of a finite set of points or of a polygon is its diameter as a set, the largest distance between any two points.
The diameter is always attained by two points of the convex hull of the input.
A trivial brute-force search can be used to find the diameter of
(assuming constant-time distance evaluations) but faster algorithms are possible for points in low dimensions.
In two dimensions, the diameter can be obtained by computing the convex hull and then applying the method of rotating calipers.
This involves finding two parallel support lines for the convex hull (for instance vertical lines through the two vertices with minimum and maximum
-coordinate) and then rotating the two lines through a sequence of discrete steps that keep them as parallel lines of support until they have rotated back to their original orientation.
The diameter is the maximum distance between any pair of convex hull vertices found as the two points of contact of the parallel lines in this sweep.
[1] For a dynamic two-dimensional point set subject to point insertions and deletions, an approximation to the diameter, with an approximation ratio that can be chosen arbitrarily close to one, can be maintained in time
[2] The exact diameter can be maintained dynamically in expected time
per operation, in an input model in which the set of points to be inserted and deleted, and the order of insertion and deletion operations, is worst-case but the point chosen to be inserted or deleted in each operation is chosen randomly from the given set.
[3] For a dynamic two-dimensional point set of a different type,
[4] In three dimensions, the diameter of a set of points can again be computed in time
[5][6] A randomized method for doing this by Clarkson and Shor uses as a subroutine a randomized incremental algorithm for finding the intersection of congruent spheres.
The algorithm repeatedly chooses a random input point, finds the farthest distance
of all other points, and therefore cannot be part of any pair with a larger distance than
Each point is eliminated when the farthest distance from it is less than or equal to
, the farthest distance from the randomly chosen point, which happens with probability
, so half of the points are eliminated in expectation in each iteration of the algorithm.
The total expected time for the algorithm is dominated by the time to find the first intersection of spheres, before the problem is simplified by eliminating any points.