Diameter (computational geometry)

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 $n$ points in time $O(n^{2})$ (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 $x$ -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. The time for this method is dominated by the time for constructing the convex hull: $O(n\log n)$ for a finite set of $n$ points, or time $O(n)$ for a simple polygon with $n$ vertices.^[1]

Dynamic 2d input

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 $O(\log ^{2}n)$ per operation.^[2] The exact diameter can be maintained dynamically in expected time $O(\log n)$ 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, $n$ points each moving linearly with fixed velocities, the time at which the points attain their minimum diameter and the diameter at that time can be computed in time $O(n\log ^{2}n)$ ^[4]

Higher dimensions

In three dimensions, the diameter of a set of points can again be computed in time $O(n\log n)$ .^[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 $\rho$ from it, intersects spheres with radius $\rho$ centered at each point, and eliminates the points contained in the resulting intersection. The eliminated points are within distance $\rho$ of all other points, and therefore cannot be part of any pair with a larger distance than $\rho$ . Each point is eliminated when the farthest distance from it is less than or equal to $\rho$ , the farthest distance from the randomly chosen point, which happens with probability ${\tfrac {1}{2}}$ , 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. This time is $O(n\log n)$ .^[5] Ramos provides a non-random algorithm by using ε-nets to derandomize a variation of the Clarkson and Shor algorithm, with the same asymptotic runtime.^[6]

In any fixed dimension $d$ , there exists an algorithm for which the exponent of $n$ in the time bound is less than two.^[7] It is also possible to approximate the diameter, to within a $(1+\varepsilon )$ approximation ratio, in time $O(n+\varepsilon ^{1/2-d})$ .^[8]

References

↑ Toussaint, Godfried T. (1983), "Solving geometric problems with the rotating calipers", in Protonotarios, E. N.; Stassinopoulos, G. I.; Civalleri, P. P. (eds.), Proceedings of MELECON '83, Mediterranean Electrotechnical Conference, Athens, Greece, 24–26 May 1983, IEEE, pp. A10.02/1–4, CiteSeerX 10.1.1.155.5671
↑ Janardan, Ravi (1993), "On maintaining the width and diameter of a planar point-set online", International Journal of Computational Geometry & Applications, 3 (3): 331–344, doi:10.1142/S021819599300021X, MR 1241923
↑ Eppstein, David (1996), "Average case analysis of dynamic geometric optimization", Computational Geometry, 6 (1): 45–68, doi:10.1016/0925-7721(95)00018-6, MR 1387673
↑ Fernández-Baca, D. (2001), "On nonlinear parametric search", Algorithmica, 30 (1): 1–11, doi:10.1007/s00453-001-0001-2, MR 1816864
1 2 Clarkson, Kenneth L.; Shor, Peter W. (1989), "Applications of random sampling in computational geometry II", Discrete & Computational Geometry, 4 (5): 387–421, doi:10.1007/BF02187740, MR 1014736
1 2 Ramos, E. A. (2001), "An optimal deterministic algorithm for computing the diameter of a three-dimensional point set", Discrete & Computational Geometry, 26 (2): 233–244, doi:10.1007/s00454-001-0029-8, MR 1843439
↑ Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in $k$ -dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663
↑ Chan, Timothy M. (2002), "Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus", International Journal of Computational Geometry and Applications, 12 (1–2): 67–85, doi:10.1142/S0218195902000748, MR 1885498

Diameter (computational geometry)

Dynamic 2d input

Higher dimensions

See also

References

Related Articles