We consider the problem of computing the diameter of a set of $n$ points in $d$-dimensional Euclidean space under Euclidean distance function. We describe an algorithm that in time $O(dn\log n +n^{2})$ finds with high probability an arbitrarily close approximation of the diameter. For large values of $d$ the complexity bound of our algorithm is a substantial improvement over the complexity bounds of previously known exact algorithms. Computing and approximating the diameter are fundamental primitives in high dimensional computational geometry and find practical application, for example, in clustering operations for image databases.
On computing the diameter of a point set in high dimensional Euclidean space
Pellegrini M
2002
Abstract
We consider the problem of computing the diameter of a set of $n$ points in $d$-dimensional Euclidean space under Euclidean distance function. We describe an algorithm that in time $O(dn\log n +n^{2})$ finds with high probability an arbitrarily close approximation of the diameter. For large values of $d$ the complexity bound of our algorithm is a substantial improvement over the complexity bounds of previously known exact algorithms. Computing and approximating the diameter are fundamental primitives in high dimensional computational geometry and find practical application, for example, in clustering operations for image databases.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
