Proximity Catch Digraphs

PCD Java Applet

This applet is prepared by Artür Manukyan.

IMPORTANT: You have to unblock this website in Java Settings. See Why are Java applications blocked? Also, to be able to run this application, please use either Internet Explorer or Mozilla Firefox.

HOW TO USE THIS APPLET

• Sample: Every time the "Sample" button is pressed, points from two classes (red and blue) are randomly generated in the space (0,1)x(0,1). You may specify the number of points in each class by changing the default values in the boxes at the bottom of the applet.
• Proximity Region: There are three proximity map families to choose in the menu. They are Arc-Slice, Proportional Edge, and Central Similarity. Upon selection, plotted proximity regions and PCDs change. With each selected proximity region, a brief description appear on the right. If either proportional edge or Central Similarity is selected, an additional box appear requesting the parameters \(r\) or \(\tau\), respectively.
• PCDs are constructed for each class: one being the Target and the other is the Non-target class. Hence, in one case Blue is the target and Red is the non-target class, and vice versa in the other case.
• Red (Blue) Delaunay: Draws the Delaunay Tasselation of Red (Blue) points. See Delaunay Triangulation .
• Red (Blue) in Convex Hull of Blue (Red): This button omits (ignores) the Blue (Red) points outside of the Red (Blue) triangulation
• Red (Blue) PCD: This button Shows the arcs (directed edges) of The PCD. PCD is associated with proximity map family selected in Proximity Region menu below.
• Red (Blue) Proximity Region: This button draws the proximity region associated with each Red (Blue) point. The type of proximity region is selected from the Proximity Region menu below.
• Red (Blue) Solution: Draws the proximity regions of points who are the members of the dominating set of Red (Blue) PCDs. Solution button appears when Red (Blue) proximity region button is active. Solution of the Red (Blue) PCDs are given with the Greedy Algorithm.

Artür Manukyan

Last modified: Wed May 13, 2015

\(r\) - Factor Proportional-Edge Proximity Map: \(N_{PE}^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})/\mathcal{Y}\), let \(v(x) \in \mathcal{Y}\) be the vertex whose region s.t. \(x \in R_{M_C}(v(x))\). See Description for 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}^{r}(x,M_{C}) = T_{PE}(x,r) \cap T(\mathcal{Y}) $$

\(\tau\)-Factor Central-Similarity Proximity Map: \(N_{CS}^{\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})/\mathcal{Y}\), let \(e(x)\) be the edge whose region satisfies \(x \in R_{M_C}(e(x))\). See Description for 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_{AS}^{\tau}(x,M_{C}) = T_{CS}(x,\tau) \cap T(\mathcal{Y}) $$

Arc-Slice Proximity Map: \(N_{AS}(.,M_{CC})\)

• Let \( \mathcal{Y}=\{y_1,y_2,y_3\} \) and let \( T(\mathcal{Y}) \) be the associated triangle with circumcenter \(M=M_{CC}\). For \(x \in T(\mathcal{Y})/\mathcal{Y}\), let \(v(x) \in \mathcal{Y}\) be the vertex whose region satisfies \(x \in R_{M_CC}(v(x))\). See Description for vertex regions. 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_{AS}(x,M_{CC}) = B(x,r(x)) \cap T(\mathcal{Y}) $$