Artur Manukyan & Elvan Ceyhan
Home Description PCD Demo References

Proximity Catch Digraphs

The proximity map \(N(\cdot): \Omega \rightarrow 2^{\Omega}\) associates with each point \(x \in \mathcal{X}\), a proximity region \(N(x) \subset \Omega\). Consider the data-random (or vertex-random) proximity catch digraph (PCD) \(D=(V,A)\) with vertex set \(V=\mathcal{X}\) and arc set \(A\) defined by \((u,v) \in A \iff \{u,v\}\subset \mathcal{X}\) and \(v \in N(u)\). The digraph \(D\) depends on the (joint) distribution of \(\mathcal{X}\), and on the map \(N(\cdot)\). The adjective proximity --- for the digraph \(D\) and for the map \(N(\cdot)\) --- comes from thinking of the region \(N(x)\) as representing those points in \(\Omega\) ``close'' to \(x\). The binary relation \(u \sim v\), which is defined as \(v \in N(u)\), is asymmetric, thus the adjacency of \(u\) and \(v\) is represented with directed edges or arcs which yield a digraph instead of a graph. Let the data set \(\mathcal{X}\) is composed of two non-empty sets, \(\mathcal{X}_0\) and \(\mathcal{X}_1\), with sample sizes \(n_0:=|\mathcal{X}_0|\) and \(n_1:=|\mathcal{X}_1|\), respectively. For \(j=0,1\), we investigate the PCD \(D_j\), associated with \(\mathcal{X}_j\) against \(\mathcal{X}_{1-j}\). Here, we specify \(\mathcal{X}_j\) as the target class and \(\mathcal{X}_{1-j}\) as the non-target class. Hence, in the definitions of our PCDs, the only difference is switching the roles of \(\mathcal{X}_0\) and \(\mathcal{X}_1\). For \(j=0\), \(\mathcal{X}_0\) becomes the target class, and for \(j=1\), \(\mathcal{X}_1\) becomes the target class.

Delaunay Tessellation

The convex hull of the non-target class \( C_H(\mathcal{X}_{1-j}) \) can be partitioned into Delaunay cells through the Delaunay tessellation of \( \mathcal{X}_{1-j} \subset \mathbb{R}^2 \). The Delaunay tessellation becomes a triangulation which partitions \( C_H(\mathcal{X}_{1-j}) \) into non intersecting triangles. For the points in the general position, the triangles in the Delaunay triangulation satisfy the property that the circumcircle of a triangle contain no points from \( \mathcal{X}_{1-j} \) except for the vertices of the triangle. In higher dimensions, Delaunay cells are \(d\)-simplices (for example, a tetrahedron in \(\mathbb{R}^3 \)). Hence, the \( C_H(\mathcal{X}_{1-j}) \) is the union of a set of disjoint \(d\)-simplices \( \{\mathfrak S_k\}_{k=1}^K \) where \(K\) is the number of \(d\)-simplices, or Delaunay cells. Each \(d\)-simplex has \(d+1\) non-coplanar vertices where none of the remaining points of \( \mathcal{X}_{1-j}\) are in the interior of the circumsphere of the simplex (except for the vertices of the simplex which are points from \( \mathcal{X}_{1-j} \)). Hence, simplices of the Delaunay tessellations are more likely to be acute (simplices with no substantially small inner angles). Note that Delaunay tessellation is the dual of the \emph{Voronoi diagram} of the set \( \mathcal{X}_{1-j} \). A Voronoi diagram is a partitioning of \( \mathbb{R}^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 \( \mathcal{X}_{1-j}\). Hence, a polytope \( V(y) \) associated with a point \( y \in \mathcal{X}_{1-j} \) is defined as $$V(y)=\{v \in \mathbb{R}^d: \lVert v-y \rVert \leq \lVert v-z \rVert \ \text{ for all } z \in \mathcal{X}_{1-j} \setminus \{y\}\}.$$ Here, \(\lVert\cdot\rVert\) stands for the usual Euclidean norm. Observe that the Voronoi diagram is unique for a fixed set of points \( \mathcal{X}_{1-j}\). A Delaunay graph is constructed by joining the pairs of points in \( \mathcal{X}_{1-j}\) whose boundaries of voronoi polytopes are intersecting. The edges of the Delaunay graph constitute a partitioning of \( C_H(\mathcal{X}_{1-j})\), hence 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 lie on the same circle of hypersphere). An illustration of the Delaunay tesselation in \( \mathbb{R}^2\) are given in the figure below.

Vertex Regions

Let \( \mathcal{Y}=\{y_1,y_2,y_3\} \subset \mathbb{R}^2 \) be three non-collinear points, and let \( T=T(\mathcal{Y})\) be the triangle formed by these points. Also, let \(e_i\) be the edge of \(T\) opposite to the vertex \(y_i\) for \(i=1,2,3\). We partition the triangle \(T\) into regions, called vertex regions. These regions are constructed based on a point, preferably a triangle center \(M \in T^o\). Vertex regions partition \(T\) into disjoint regions (only intersecting on the boundary) such that each vertex region has only one of vertices \( \{y_1,y_2,y_3\}\) associated with it. In particular, \(M\)-vertex regions are classes of vertex regions, which are constructed by the lines from each vertex \(y_i\) to \(M\). These lines cross the edge \(e_i\) at point \(M_i\). By connecting \(M\) with each \(M_i\), we attain regions associated with vertices \( \{y_1,y_2,y_3\}\). \(M\)-vertex region of \( y_i\) is denoted by \(R_M(y_i)\) for \(i=1,2,3\). For the sake of simplicity, we will refer \(M\)-vertex regions as vertex regions.

Edge Regions

Let \(\mathcal{Y}=\{y_1,y_2,y_3\} \subset \mathbb{R}^2\) be the set of non-collinear points that constitutes some inner triangle \(T=T(\mathcal{Y})\) of \(C_H(\mathcal{X}_{1-j})\). Let \(e_i\) be the edge opposite to the vertex \(y_i\) for \(i=1,2,3\). We partition the triangle \(T\) into regions, namely edge regions. These regions are constructed based on a point, preferably a triangle center \(M \in T^o\). Here, \(T^o\) is the interior of the triangle \(T\). Edge regions are associated with the edges opposite to each vertex of \(\mathcal{Y}\). We attain the edge regions by joining each \(y_i\) with \(M\), also referred as \(M\)-edge regions. \(M\)-edge region of \(e_i\) is denoted by \(R_M(e_i)\) for \(i=1,2,3\). Observe that in \(M\)-edge regions, the interiors of these regions are disjoint. For the sake of simplicity, we will refer \(M\)-edge regions as edge regions.

Minimum Dominating Sets and the Greedy Algorithm

In general, a digraph \(D=(V,A)\) of order \(n=|V|\), a vertex \(v\) dominates itself and all vertices of the form \(\{u:\,(v,u) \in A\}\). A dominating set , \(S_D\), for the digraph \(D\) is a subset of \(V\) such that each vertex \(v \in V\) is dominated by a vertex in \(S_D\). A minimum dominating set (MDS), \(S_{MD}\), is a dominating set of minimum cardinality, and the domination number , \(\gamma(D)\), is defined as \(\gamma(D):=|S_{MD}|\). If an MDS is of size one, we call it a dominating point . Finding an MDS is, in general, an NP-hard optimization problem. However, an approximate MDS can be obtained in \(O(n^2)\) using a well-known greedy algorithm given in the algorithm below. PCDs using \(N(\cdot)=N_S(\cdot,\theta)\) and \(N(\cdot)=N_{CS}(\cdot,\tau)\) are examples of such digraphs. The existence of polynomial time algorithm for find the MDS of PCDs with proximity maps \( N_{CS}(\cdot,\tau)\) is still an open problem. \(D[H]\) is the digraph induced by the set of vertices \( H \subseteq V\).

Maintained by

Artur Manukyan

Last modified: Nov 21, 2017