﻿ Description

Description

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