A Practical Approach for Computing the Diameter of a Point Set

2025/05/16 by Sariel Har-Peled, Har-Peled, Sariel · 1 citation
Computer Science · Mathematics · #Algorithm design #Approximation algorithm #Computation #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #Key (lock) #Mathematical Approximation and Integration #Point (geometry) #Set (abstract data type) #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.2505.11317

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2025/05/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

We present an approximation algorithm for computing the diameter of a point-set in \Re^d. The new algorithm is sensitive to the ``hardness'' of computing the diameter of the given input, and for most inputs it is able to compute the exact diameter extremely fast. The new algorithm is simple, robust, has good empirical performance, and can be implemented quickly. As such, it seems to be the algorithm of choice in practice for computing/approximating the diameter.

Citations

• Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions

Cited by

• New Constructions of SSPDs and their Applications

Related

• Fast Approximation and Randomized Algorithms for Diameter
• Approximate Minimum Diameter
• Approximating the Diameter of Planar Graphs in Near Linear Time
• On particular diameter bounds for integral point sets in higher dimensions
• The Geodesic Diameter of Polygonal Domains