Proximity Map Families

We briefly define three proximity map families. Let Ω = ℝ^d and let 𝒴_m = {y₁, y₂, …, y_m} be m points in general position in ℝ^d and T_i be the i^th Delaunay cell for i = 1, 2, …, J_m, where J_m is the number of Delaunay cells based on 𝒴_m. Let 𝒳_n be a set of iid random variables from distribution F in ℝ^d with support 𝒮(F) ⊆ 𝒞_H(𝒴_m) where 𝒞_H(𝒴_m) stands for the convex hull of 𝒴_m. For illustrative purposes, we focus on ℝ² where a Delaunay tessellation is a triangulation, provided that no more than three 𝒴 points are cocircular (i.e., lie on the same circle). Furthermore, for simplicity, let 𝒴₃ = {y₁, y₂, y₃} be three non-collinear points in ℝ² and T(𝒴₃) = T(y₁, y₂, y₃) be the triangle with vertices 𝒴₃. Let 𝒳_n be a set of iid random variables from F with support 𝒮(F) ⊆ T(𝒴₃).

Arc-Slice Proximity Maps and Associated Proximity Regions

We define the arc-slice proximity region with M-vertex regions for a point x ∈ T(𝒴₃) as follows; see also Figure @ref(fig:NAS-example). Using a center M of T(𝒴₃), we partition T(𝒴₃) into “vertex regions” R_V(y₁), R_V(y₂), and R_V(y₃). If M is the circumcenter of T(𝒴₃), we use perpendicular line segments from M to the opposite edges to form the vertex regions. If M is not the circumcenter but is in the interior of T(𝒴₃), we use line segments from M to the opposite edges as extensions of the lines joining the vertices and M to form the vertex regions. For x ∈ T(𝒴₃) \ 𝒴₃, let v(x) ∈ 𝒴₃ be the vertex in whose region x falls, so x ∈ R_V(v(x)). If x falls on the boundary of two vertex regions, we assign v(x) arbitrarily to one of the adjacent regions. The arc-slice proximity region is $N_{AS}(x):=\overline B(x,r(x)) \cap T(\mathcal{Y}_3)$ where $\overline B(x,r(x))$ is the closed ball centered at x with radius r(x) := d(x, v(x)). To make the dependence on M explicit, we also use the notationN_AS(⋅, M). A natural choice for the radius is r(x) := min_{y ∈ 𝒴}d(x, y) which implicitly uses the CC-vertex regions, since x ∈ R_CC(y) iff y = arg min_{u ∈ 𝒴}d(x, u). See Figure @ref(fig:NAS-example) for N_AS(x, M_CC) with x ∈ R_CC(y₂) and Ceyhan (2010) for more detail on AS proximity regions.

(#fig:NAS-example) Illustration of the construction of arc-slice proximity region, N_AS(x, M_CC) with an x ∈ R_CC(y₂).

Proportional-Edge Proximity Maps and Associated Proximity Regions

We define the proportional-edge proximity map with expansion parameter r ≥ 1 as follows; see also Figure @ref(fig:NPE-example). Using a center M of T(𝒴₃), we partition T(𝒴₃) into “M-vertex regions” as in Section @ref(sec:PE-PCD-construction). Let e(x) be the edge of T(𝒴₃) opposite v(x), the vertex whose region contains x, ℓ(x) be the line parallel to e(x) through x, and d(v(x), ℓ(x)) be the Euclidean distance from v(x) to ℓ(x). For r ∈ [1, ∞), let ℓ_r(x) be the line parallel to e(x) such that d(v(x), ℓ_r(x)) = rd(v(x), ℓ(x)) and d(ℓ(x), ℓ_r(x)) < d(v(x), ℓ_r(x)). Let T_PE(x, r) be the triangle similar to and with the same orientation as T(𝒴₃) having v(x) as a vertex and ℓ_r(x) as the opposite edge. Then the proportional-edge proximity region N_PE(x, r) is defined to be T_PE(x, r) ∩ T(𝒴₃). To make the dependence on M explicit, we also use the notationN_PE(x, r, M). A natural choice for the center is the center of mass (CM) yielding the CM-vertex regions, which have the same area (equaling one-third of the area of T(𝒴₃)). Notice that r ≥ 1 implies x ∈ N_PE(x, r). Note also that lim_{r → ∞}N_PE(x, r) = T(𝒴₃) for all x ∈ T(𝒴₃) \ 𝒴₃, so we define N_PE(x, ∞) = T(𝒴₃) for all such x. For x ∈ 𝒴₃, we define N_PE(x, r) = {x} for all r ∈ [1, ∞]. See Ceyhan and Priebe (2005), Ceyhan, Priebe, and Wierman (2006), and Ceyhan (2014) for more detail.

(#fig:NPE-example) Illustration of the construction of proportional-edge proximity region, N_PE(x, r = 2) (shaded region) for an x ∈ R_V(y₁) where d₁ = d(v(x), ℓ(v(x), x)) and d₂ = d(v(x), ℓ₂(v(x), x)) = 2 d(v(x), ℓ(v(x), x)).

Central Similarity Proximity Maps and Associated Proximity Regions

We define the central similarity proximity map with expansion parameter τ > 0 as follows; see also Figure @ref(fig:NCS-example). Let e_j be the edge opposite vertex y_j for j = 1, 2, 3, and let “M-edge regions” R_E(e₁), R_E(e₂), R_E(e₃) partition T(𝒴₃) using line segments from the center M in the interior of T(𝒴₃) to the vertices. For x ∈ (T(𝒴₃))^o, let e(x) be the edge in whose region x falls; x ∈ R_E(e(x)). If x falls on the boundary of two edge regions we assign e(x) arbitrarily. For τ > 0, the central similarity proximity region N_CS(x, τ) is defined to be the triangle T_CS(x, τ) ∩ T(𝒴₃) with the following properties:

1. For τ ∈ (0, 1], the triangle T_CS(x, τ) has an edge e_τ(x) parallel to e(x) such that d(x, e_τ(x)) = τ d(x, e(x)) and d(e_τ(x), e(x)) ≤ d(x, e(x)) and for τ > 1, d(e_τ(x), e(x)) < d(x, e_τ(x)) where d(x, e(x)) is the Euclidean distance from x to e(x),

2. the triangle T_CS(x, τ) has the same orientation as and is similar to T(𝒴₃),

3. the point x is at the center of mass of T_CS(x, τ).

Note that (i) implies that the expansion parameter is τ, (ii) implies “similarity”, and (iii) implies “central” in the name, (parameterized) central similarity proximity map. To make the dependence on M explicit, we also use the notationN_CS(x, τ, M). A natural choice for the center is the center of mass (CM) yielding the CM-edge regions, which have the same area (equaling one-third of the area of T(𝒴₃)). Notice that τ > 0 implies that x ∈ N_CS(x, τ) and, by construction, we have N_CS(x, τ) ⊆ T(𝒴₃) for all x ∈ T(𝒴₃). For x ∈ ∂(T(𝒴₃)) and τ ∈ (0, ∞], we define N_CS(x, τ) = {x}. For all x ∈ T(𝒴₃)^o the edges e_τ(x) and e(x) are coincident iff τ = 1. Note also that lim_{τ → ∞}N_CS(x, τ) = T(𝒴₃) for all x ∈ (T(𝒴₃))^o, so we define N_CS(x, ∞) = T(𝒴₃) for all such x. The central similarity proximity maps in Ceyhan and Priebe (2003) and Ceyhan, Priebe, and Marchette (2007) are N_CS(⋅, τ) with τ = 1 and τ ∈ (0, 1], respectively, and in Ceyhan (2014) with τ > 1.

(#fig:NCS-example) Illustration of the construction of central similarity proximity region, N_CS(x, τ = 1/2) (shaded region) for an x ∈ R_E(e₃) where $h_2=d(x,e_3^\tau(x))=\frac{1}{2}\,d(x,e(x))$ and h₁ = d(x, e(x)).

Delaunay Tessellation

The convex hull of the non-target class C_H(𝒴_m) can be partitioned into Delaunay cells through the Delaunay tessellation of 𝒴_m ⊂ ℝ^d. The Delaunay tessellation becomes a triangulation in ℝ² which partitions C_H(𝒴_m) into non-intersecting triangles. For 𝒴 points in general position, the triangles in the Delaunay triangulation satisfy the property that the circumcircle of a triangle contain no 𝒴 points except for the vertices of the triangle. In higher dimensions (i.e., d > 2), Delaunay cells are d-simplices (for example, a tetrahedron in ℝ³). Hence, the C_H(𝒴_m) is the union of a set of disjoint d-simplices {𝔖_k}_k = 1^K where K is the number of d-simplices, or Delaunay cells. Each d-simplex has d + 1 non-co(hyper)planar vertices where none of the remaining points of 𝒴_m are in the interior of the circumsphere of the simplex (except for the vertices of the simplex which are points from 𝒴_m). Hence, simplices of the Delaunay tessellations are more likely to be acute (simplices will not have substantially large inner angles). Note that Delaunay tessellation is the dual of the Voronoi diagram of the points 𝒴_m. A Voronoi diagram is a partitioning of ℝ^d into convex polytopes such that the points inside each polytope is closer to the point associated with the polytope than any other point in 𝒴. Hence, a polytope V(y) associated with a point y ∈ 𝒴_m is defined as V(y) = {v ∈ ℝ^d : ∥v − y∥ ≤ ∥v − z∥  for all z ∈ 𝒴_m \ {y}}.

Here, ∥⋅∥ stands for the usual Euclidean norm. Observe that the Voronoi diagram is unique for a fixed set of points 𝒴_m. A Delaunay graph is constructed by joining the pairs of points in 𝒴_m whose boundaries of Voronoi polytopes have nonempty intersections. The edges of the Delaunay graph constitute a partitioning of C_H(𝒴_m) providing the Delaunay tessellation. By the uniqueness of the Voronoi diagram, the Delaunay tessellation is also unique (except for cases where d + 1 or more points lying on the same hypersphere). Run the below code for an illustration of Delaunay triangulation of 20 uniform 𝒴 points in the unit square (0, 1) × (0, 1). More detail on Voronoi diagrams and Delaunay tessellations can be found in Okabe et al. (2000).

ny<-20; 

set.seed(1)
#Xp<-cbind(runif(nx),runif(nx))
Yp<-cbind(runif(ny),runif(ny))

#oldpar <- par(no.readonly = TRUE)
plotDelaunay.tri(Yp,Yp,xlab="",ylab="",main="Delaunay Triangulation of Y points")

Graph Invariants: Arc Density and Domination Number

Arc Density: The arc density of a digraph D = (V, A) of order |V| = n, denoted ρ(D), is defined as $$ \rho(D) = \frac{|A|}{n(n-1)} $$ where |⋅| stands for set cardinality (Janson, Łuczak, and Ruciński (2000)). Thus ρ(D) represents the ratio of the number of arcs in the digraph D to the number of arcs in the complete symmetric digraph of order n, which has n(n − 1) arcs.

If $X_1,X_2,\ldots,X_n \stackrel{iid}{\sim} F$, then the relative density of the associated data-random PCD, denoted ρ(𝒳_n; h, N), is a U-statistic, $$\rho(\mathcal{X}_n;h,N) = \frac{1}{n(n-1)} \underset{i<j}{\sum\sum}h(X_i,X_j;N) $$

with I{⋅} being the indicator function. We denote h(X_i, X_j; N) as h_ij for brevity of notation. Since the digraph is asymmetric, h_ij is defined as the number of arcs in D between vertices X_i and X_j, in order to produce a symmetric kernel with finite variance (Lehmann (2004)).

See Ceyhan, Priebe, and Wierman (2006), Ceyhan, Priebe, and Marchette (2007), and Ceyhan (2014) for arc density of PE-PCDs and its use for spatial interaction for 2D data; and Ceyhan (2012) and Ceyhan (2016) for arc density of PE-PCDs for 1D data and its use for testing uniformity.

Domination Number: In a digraph D = (V, A), a vertex v ∈ V dominates itself and all vertices of the form {u : (v, u) ∈ A}. A dominating set S_D for the digraph D is a subset of V such that each vertex v ∈ V is dominated by a vertex in S_D. A minimum dominating set S_D^* is a dominating set of minimum cardinality and the domination number γ(D) is defined as γ(D) := |S_D^*| (see, e.g., Lee (1998)). If a minimum dominating set is of size one, we call it a dominating point. Note that for |V| = n > 0, 1 ≤ γ(D) ≤ n, since V itself is always a dominating set. See Ceyhan and Priebe (2005) and Ceyhan (2011) for the domination number and its use for testing spatial interaction patterns in 2D data and Ceyhan (2020) for testing uniformity of 1D data.

Geometry Invariance of Arc Density and Domination Number: Let 𝒰(T(𝒴₃)) be the uniform distribution on T(𝒴₃). If F = 𝒰(T(𝒴₃)), a composition of translation, rotation, reflections, and scaling, denoted ϕ_b(T(𝒴₃)), will take any given triangle T(𝒴₃) to the standard basic triangle T_b = T((0, 0), (1, 0), (c₁, c₂)) with 0 < c₁ ≤ 1/2, c₂ > 0, and (1 − c₁)² + c₂² ≤ 1, preserving uniformity. That is, if X ∼ 𝒰(T(𝒴₃)) is transformed in the same manner to, say X′ = ϕ_b(X), then we have X′ ∼ 𝒰(T_b). In fact this will hold for data from any distribution F up to scale. Furthermore, T_b can be transformed to the standard equilateral triangle T_e = T(A, B, C) with vertices A = (0, 0), B = (1, 0), and $C=(1/2,\sqrt{3}/2)$ by a transformation ϕ_e and ϕ_e(X′) ∼ 𝒰(T_e). That is uniform points in any triangle can be mapped to points uniformly distributed in the standard equilateral triangle by a composition of ϕ_b and ϕ_e (in the form ϕ_e ∘ ϕ_b).

The distribution of the domination number and arc density for AS-PCDs do not change for uniform data in a triangle T(𝒴₃) when the data points are transformed to (uniform) points in the standard basic triangle T_b (using ϕ_b) but not when ϕ_e is applied to the uniform data in T_b. So, one can focus on T_b for computations and derivations regarding the domination number and arc density of AS-PCD for uniform data. On the other hand, the distribution of the domination number and arc density for PE- and CS-PCDs do not change for uniform data in a triangle T(𝒴₃) when the data points are transformed to (uniform) points in the standard equilateral triangle T_e (using ϕ_e ∘ ϕ_b). That is, distribution of these graph quantities are geometry invariant for uniform data in triangles. So, one can focus on T_e for computations and derivations regarding the PE- and CS-PCD quantities for uniform data. A similar geometry invariance holds in 3D setting for uniform data in any tetrahedron being transformed to the standard regular tetrahedron for PE- and CS-PCDs. Therefore, the pcds package has functions customized only for one simplex (i.e., one interval in ℝ, one triangle in ℝ², and one tetrahedron in ℝ³). However, we don’t cover these functions here, as (i) they serve as utility functions in the more realistic case of multiple simplices (e.g., multiple triangles occur when there are m ≥ 4 𝒴 points) and (ii) they are mainly used for simulations or verifications or illustrations when 𝒳 points are restricted to one simplex. See the vignette files “VS2.1 - Illustration of PCDs in One Triangle”, “VS2.2 - Illustration of PCDs in One Interval”, and “VS2.3 - Illustration of PCDs in One Tetrahedron”.