Computational Geometry
Department of Computer Science
Proximity Depth

For any proximity graph the proximity graph depth is defined using a point's minimum path length along graph edges to the convex hull of the data set S.

Proximity Graph Depth
The Proximity Graph Depth of a point x relative to a set S = (X_1 ... X_n) is the minimum number of edges in the proximity graph of S that must be traversed in order to travel from x to any point on the convex hull of S (see Figure).
Proximity graphs are graphs in which points close to each other by some definition of closeness are connected [6]. We concentrate our analysis on the Delaunay triangulation [3] and beta-skeletons [7] which are a parameterized family of proximity graphs, which include as a special case the Gabriel graph and the relative neighborhood graph. We denote by delta(p, q) the Euclidean distance between points p and q.
Exploring a proximity depth calculation. The edge-distance from each data point to a convex-hull point is illustrated using highlighted trees. Two normal clouds with 250 points separated horizontally by 6 standard deviations.
Delaunay Triangulation
The Delaunay Triangulation (DT) of a d-dimensional point set S is the simplicial decomposition of the convex hull of S such that the d-sphere defined by the points of every simplex in the decomposition contains no point r in S [3]. This decomposition is the dual of the Voronoi diagram and is unique for every set of points [1].
Beta Skeleton
The Beta Skeleton of a point set S in R^d is the set of edges joining beta-neighbors.
Points p and q are lune-based beta-neighbors for beta >= 1, if an only if the lune defined by the intersection of the spheres centered at (1 - (beta / 2))p+(beta * 2)q and (1 - (beta / 2))q+(beta/2)p, each with radius (beta/2) \ delta(p, q), contains no point r in S.
Points p and q are circle-based beta-neighbors for beta >= 1, if and only if the lune defined by the union of the two spheres of radius (beta/2) \ delta(p, q) contains no point r in S.
Points p and q are beta-neighbors for beta < 1, if an only if the lune defined by the intersection of the two sphere of radius (beta/2) \ delta(p, q) which contain p and q in their boundary contains no point r in S (for beta < 1, the lune-based and circle-based neighbors are identical).

For beta > 1, the lune-based beta-skeletons are planar and monotonic with respect to beta: G(beta_1(S)) is a subset of G(beta_2(S)), for beta_1 < beta_2. The Gabriel Graph (GG) [4] is the lune-based 1-skeleton while the relative neighborhood graph (RNG) [11] is the lune-based 2-skeleton. The circle-based beta-skeletons for beta > 1, are not necessarily planar and have a reverse monotonic relation with respect to beta: G(beta_1(S)) is a subset of G(beta_2(S)), for beta_1 > beta_2.

For beta < 1, as beta becomes smaller, the beta skeleton tends towards the complete graph.

Overall Complexity

The depths of all points in a proximity graph can be determined in linear time in the number of edges in the graph by using a breadth-first search (BFS) of the graph, beginning at every point on the convex hull of S (see Figure).

Assignment of all depths of a point set is accomplished by

1. Computation of the proximity graph;
2. Location of all convex hull points; and
3. Breadth-first search of the proximity graph.

In two dimensions there are optimal O(n log n) time algorithms to compute the DT [3], the circle-based beta-skeletons for beta >= 1, and the lune-based beta-skeleton for 1 <= beta <= 2 [7, 8, 5]. The lune-based beta-skeletons for beta > 2 and the beta-skeletons for beta < 1 can be computed in optimal O(n^2) time [7, 5]. Points on the convex hull can be determined in O(n log n) time [10], for an overall time requirement of O(n log n) for the DT and O(n^2) or O(nlog(n)) for the beta-skeleton.

In dimensions higher than 2, the DT can be calculated in O(n^(ceiling(d / 2)) time [2]. The beta-skeletons require checking n points for interiority on n^2 lunes, which requires a distance calculation for a total of O(dn^3) time. More efficient algorithms for specific graphs like the GG or RNG or for 3-dimensional space are known [6]. The set of points on the convex hull of the set can be found in O(mn) time, where m is the number of extreme points [9]. Breadth-first search then requires linear time in the size of the proximity graph.

Clearly, the time complexity in higher dimensions is dominated by the computation of the proximity graph itself. Assignment of all depths, then, has a total complexity of O(n^ceiling(d / 2)) time for Delaunay depth and O(dn^3) time for the beta-skeleton depths. The exponential dependence on dimension for calculating Delaunay depth makes it impractical for use in high dimensions.

References
[1] Algorithms in Computational Geometry. H. Edelsbrunner. Springer-Verlag, 1978.
[2] Voronoi diagrams and arrangements. H. Edelsbrunner and R. Seidel. Discrete and Computational Geometry, 1:25–44, 1986.
[3] Voronoi diagrams and Delaunay triangulations. S. Fortune. In Handbook of discrete and computational geometry, CRC Press Ser. Discrete Math. Appl., pages 377–388. CRC Press, Inc., Boca Raton, FL, USA, 1997.
[4] A new statistical approach to geographic variation analysis. K. R. Gabriel and R. R. Sokal. Systematic Zoology, 18:259–278, 1969.
[5] Optimal and suboptimal robust algorithms for proximity graphs. Ferran Hurtado, Giuseppe Liotta, and Henk Meijer. Comput. Geom., 25(1-2):35–49, 2003. Special issue on the European Workshop on Computational Geometry—CG01 (Berlin).
[6] Relative neighborhood graphs and their relatives. J. W. Jaromczyk and G. T. Toussaint. Proc. IEEE, 80(9):1502–1517, sep 1992.
[7] A framework for computational morphology. D. G. Kirkpatrick and J. D. Radke. In G. Toussaint, editor, Computational geometry, pages 217–248. North-Holland, 1985.
[8] A linear-time construction of the relative neighborhood graph from the Delaunay triangulation. Andrzej Lingas. Comput. Geom., 4(4):199–208, 1994.
[9] Enumerating extreme points in higher dimensions. Thomas Ottmann, Sven Schuierer, and S. Soundaralakshmi. In Symposium on Theoretical Aspects of Computer Science, pages 562–570, 1995.
[10] Convex hulls of finite sets of points in two and three dimensions. F.P. Preparata and S.J. Hong. Commun. ACM, 20(2):87–93, 1977.
[11] The relative neighborhood graph of a finite planar set. G.T. Toussaint. Pattern Recognition, 12:261–268, 1980.