Proximity Catch Digraphs

HOW TO USE THIS DEMO

• PCDs are constructed for each class: one being the target and the other is the non-target class. Hence, e.g. Blue points can be the target class and Red points can be the non-target class, and vice versa. See Proximity Catch Digraphs.
• Target Class: When selecting the Target Class as Blue (Red), the non-target class is automatically set to Red (Blue). Also, the Delaunay Tesselation is drawn for the Red (Blue) points. Proximity Regions, PCDs and MDSs are also presented for the Red (Blue) points.
• Sample: When the "Sample" button is pressed, points from two classes (i.e., red and blue points) are randomly generated in (0,620)x(0,380). You may specify the number of points in each class by changing the default values in the boxes at the bottom of the demo.
• Proximity Map: There are three proximity map families to choose in the menu. They are Spherical, Proportional Edge (PE), and Central Similarity (CS) proximity maps. When selected, plotted proximity regions and PCDs change. With each selected proximity region, a brief description appear on the right. You may change the parameters \(r\) or \(\tau\) at boxes at the right side of the demo.
• Delaunay: Draws the Delaunay Tasselation of the Red (Blue) points. Not valid for spherical proximity map. See Delaunay Tesselation.
• Proximity Region: This button draws the proximity region associated with each Blue (Red) point. The type of proximity region is selected from the Proximity Region menu below.
• PCD: This button shows the arcs (i.e. directed edges) of the PCD of the Blue (Red) points. The PCD is associated with proximity map family selected in Proximity Region menu below. That is, for example, if PE proximity map is selected, the corresponding digraph is the PE-PCD.
• MDS: Highlights the Blue (Red) points of the minimum dominating set (MDS) of Blue (Red) PCDs. If the proximity regions button is selected, draws the proximity regions of points which are the members of the MDS. MDSs are equivalent to solutions of Class Cover Problem with minimum number of Proximity Regions (see Cannon and Cowen (2000) for more on the class cover problem). MDSs of the Blue (Red) PCDs are given with the Greedy Algorithm.

Maintained by A. Manukyan & E. Ceyhan  (demo is prepared by A. Manukyan)

Proportional-Edge Proximity Map: \(N_{PE}(\cdot,r,M)\)

• Let \( r \in [1,\infty) \) and \( \mathcal{Y}=\{y_1,y_2,y_3\} \) and \(M=M_c\) is the median (center of mass) of the triangle \(T(\mathcal{Y})\). For \(x \in T(\mathcal{Y})\setminus \mathcal{Y}\), let \(v(x) \in \mathcal{Y}\) be the vertex whose region s.t. \(x \in R_{M_C}(v(x))\). See vertex regions .
• Let \(e(x)\) be the edge opposite to the vertex \(v(x)\), \(l(v(x),x)\) be the parallel line to \(e(x)\) through \(x\), \(d(v(x),l(v(x),x))\) be the Euclidean distance between \(v(x)\) and \(l(v(x),x)\), and let \(l_r(v(x),x)\) be the line parallel to \(e(x)\): $$ d(v(x),l_r(v(x),x))=rd(v(x),l(v(x),x)) $$

  and

  $$ d(l(v(x),x),l_r(v(x),x)) < d(v(x),l(v(x),x)). $$
• Let \( T_{PE}(x,r) \) be the triangle similar to and with the same orientation as \( T(\mathcal{Y}) \) having \(v(x)\) as a vertex and \(l_r(v(x),x)\) as the opposite vertex. Here:
$$ N_{PE}(x,r,M_{C}) = T_{PE}(x,r) \cap T(\mathcal{Y}) $$

Central-Similarity Proximity Map: \(N_{CS}(\cdot,\tau,M)\)

• Let \( \tau \in (0,\infty) \), \( \mathcal{Y}=\{y_1,y_2,y_3\} \) and \(M=M_c\) is the median (center of mass) of the triangle \(T(\mathcal{Y})\). For \(x \in T(\mathcal{Y})\setminus \mathcal{Y}\), let \(e(x)\) be the edge whose region satisfies \(x \in R_{M_C}(e(x))\). See edge regions.
• Let \(e_{\tau}(x)\) be the line parallel to \(e(x)\) s.t. $$ d(x,e_{\tau}(x))=\tau d(x,e_(x)) $$

  and

  $$ d(e_{\tau}(x),e(x)) \leq \tau d(x,e(x)), \tau \leq 1$$ $$ d(e_{\tau}(x),e(x)) > \tau d(x,e(x)), \tau > 1$$
• Let \(T_{CS}(x,\tau)\) be the triangle similar to \( T(\mathcal{Y})\), and \(x\) is its center. Here:
$$ N_{CS}(x,\tau,M_{C}) = T_{CS}(x,\tau) \cap T(\mathcal{Y}) $$

Spherical Proximity Map: \(N_{S}(\cdot)\)

• Let \( \mathcal{X}=\{x_1,x_2, \cdots, x_n\} \), \( \mathcal{Y}=\{\mathsf{y}_1,\mathsf{y}_2,\cdots,\mathsf{y}_m\} \) be two classes, and let \( d(x,y)\) is the \(L_2\) metric (Euclidean) distance. Here:
$$v(x) = \arg\min_{y \in \mathcal{Y}} d(x,y)$$
• \(B(x,r(x))\) is the ball centered on \(x\) and with radius \(r(x)=d(x,v(x))\). Thus;
$$N_{S}(x) = B(x,r(x)).$$