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).

- 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

- Computation of the proximity graph;
- Location of all convex hull points; and
- 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.

[2] Voronoi diagrams and arrangements.
Discrete and Computational Geometry, 1:25–44, 1986.

[3] Voronoi diagrams and Delaunay triangulations.
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.
Systematic Zoology, 18:259–278, 1969.

[5] Optimal and suboptimal robust algorithms for proximity graphs.
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.
Proc. IEEE, 80(9):1502–1517, sep 1992.

[7] A framework for computational morphology.
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.
Comput. Geom., 4(4):199–208, 1994.

[9] Enumerating extreme points in higher dimensions.
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.
Commun. ACM, 20(2):87–93, 1977.

[11] The relative neighborhood graph of a finite planar set.
Pattern Recognition, 12:261–268, 1980.