# Proximity Catch Digraphs

This demo is prepared by Artur Manukyan.

# of Blue:

# of Red:

Target Class =

Non-target Class = Red

Proximity Map =

Proximity Regions
PCD

MDS

#### HOW TO USE THIS DEMO

• 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. See Proximity Catch Digraphs .
• Target Class: Upon selecting the Target Class as Blue (Red), the non-target class is automatically set to Red (Blue). Also, the Delaunay Tesselation is drawn for Red (Blue) points. Proximity Regions, PCDs and MDSs are drawn for Red (Blue) points.
• Sample: Upon the "Sample" button is pressed, points from two classes (red and blue) 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). Upon selection, 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 on the right side of the demo.
• Delaunay: Draws the Delaunay Tasselation of 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 (directed edges) of the PCD of Blue (Red) points. The PCD is associated with proximity map family selected in Proximity Region menu below.
• 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. MDSs of the Blue (Red) PCDs are given with the Greedy Algorithm.

Maintained by

Artur Manukyan

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

• Let $$\mathcal{X}_j=\{x_1,x_2, \cdots, x_n\}$$, $$\mathcal{X}_{1-j}=\{y_1,y_2,\cdots,y_m\}$$ be two classes, and let $$d(x,y)$$ is the $$L_2$$ metric (euclidean) distance. W.L.O.G., here:
• $$v(x) = \arg\min_{y \in \mathcal{X}_{1-j}} d(x,y)$$
• $$B(x,r(x))$$ is the ball (box, for $$L_{\infty}$$ and polytope, for $$L_1$$) centered on $$x$$ and with radius $$r(x)=d(x,v(x))$$. Thus;
• $$N_{S}(x) = B(x,r(x))$$