Reducing the Computational Complexity of the Eccentricity Transform of a Tree

Abstract

This paper proposes a novel approach to reduce the computational complexity of the eccentricity transform (ECC) for graph-based representation and analysis of shapes. The ECC assigns to each point within a shape its geodesic distance to the furthest point, providing essential information about the shape’s geometry, connectivity, and topology. Although the ECC has proven valuable in numerous applications, its computation using traditional methods involves heavy computational complexity. To overcome this limitation, we present a method that computes the ECC of a tree, significantly reducing the computational complexity from O(n2log(n) ) to O(b), where n and b are the numbers of vertices and branching points in the tree, respectively. Our method begins by computing the ECC for tree structures, which are simpler representations of shapes. Subsequently, we introduce the concept of a 3D curve that corresponds to a smooth shape without holes, enabling the computation of the ECC for more complex shapes. By leveraging the 3D curve representation, our method provides an upper-bound approximation of the ECC, which can be effectively utilized in various applications. The proposed approach not only preserves the valuable properties of the ECC but also significantly reduces the computational burden, making it a more efficient and practical solution for graph-based representation and analysis of shapes in both 2D and 3D contexts.