Misplaced Pages

Revision as of 00:40, 27 December 2024

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 ${\displaystyle n}$ points in time ${\displaystyle 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 gives time ${\displaystyle O(n\log n)}$ for a finite point set, or time ${\displaystyle O(n)}$ for a simple polygon.
• 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 ${\displaystyle O(\log ^{2}n)}$ per operation. The exact diameter can be maintained dynamically in expected time ${\displaystyle 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.
• For a dynamic two-dimensional point set of a different type, ${\displaystyle 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 ${\displaystyle O(n\log ^{2}n)}$
• In three dimensions, the diameter of a set of points can again be computed in time ${\displaystyle O(n\log n)}$.
• In any fixed dimension ${\displaystyle d}$, there exists an algorithm for which the exponent of ${\displaystyle n}$ in the time bound is less than two. It is also possible to approximate the diameter, to within a ${\displaystyle (1+\varepsilon )}$ approximation ratio, in time ${\displaystyle O(n+\varepsilon ^{1/2-d})}$.

See also

• Kinetic diameter (data), the algorithmic problem of maintaining the diameter of moving points
• Minimum-diameter spanning tree, a different notion of diameter for low-dimensional points based on the graph diameter of a spanning tree

References

1. 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
2. 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
3. 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
4. Fernández-Baca, D. (2001), "On nonlinear parametric search", Algorithmica, 30 (1): 1–11, doi:10.1007/s00453-001-0001-2, MR 1816864
5. 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
6. 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
7. Yao, Andrew Chi Chih (1982), "On constructing minimum spanning trees in ${\displaystyle k}$-dimensional spaces and related problems", SIAM Journal on Computing, 11 (4): 721–736, doi:10.1137/0211059, MR 0677663
8. 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

• Length
• Geometric algorithms