\section{Introduction}
\label{sec:introduction}
The \emph{proximity catch digraphs} (PCDs)
are a special type of \emph{proximity graphs} which were introduced by
\cite{toussaint:1980}.
A \emph{digraph} is a directed graph with
vertices $V$ and arcs (directed edges) each of which is from one
vertex to another based on a binary relation. Then the pair $(p,q)
\in V \times V$ is an ordered pair which stands for an arc (directed
edge) from vertex $p$ to vertex $q$. For example, the \emph{nearest
neighbor (di)graph} of \cite{paterson:1992} is a proximity digraph.
 The nearest neighbor digraph has the vertex set $V$
and $(p,q)$ as an arc iff $q$ is a nearest neighbor of $p$.

Our PCDs are based on the proximity maps which are defined in a
fairly general setting. Let $(\Omega,\mathcal{M})$ be a measurable space.
The \emph{proximity map} $N(\cdot)$ is defined as
$N:\Omega \rightarrow 2^\Omega$, where $2^\Omega$ is the power set of $\Omega$.
The \emph{proximity region} of $x \in \Omega$, denoted
$N(x)$, is the image of $ x \in \Omega$ under $N(\cdot)$.
The points in $N(x)$ are thought of as being ``closer" to $x \in \Omega$ than
are the points in $\Omega \setminus N(x)$.
Hence the term ``proximity" in the name \emph{proximity catch digraph}.
Proximity maps are the building blocks of the \emph{proximity graphs} of
\cite{toussaint:1980}; an extensive survey on proximity maps and graphs
is available in \cite{jaromczyk:1992}.

The \emph{proximity catch digraph} $D$ has the vertex set
$\mathcal{V}=\bigl\{ p_1,\ldots,p_n \bigr\}$; and the arc set $\mathcal{A}$ is defined
by $(p_i,p_j) \in \mathcal{A}$ iff $p_j \in N(p_i)$ for $i\not=j$. Notice
that the proximity catch digraph $D$ depends on the \emph{proximity}
map $N(\cdot)$ and if $p_j \in N(p_i)$, then we call $N(p_i)$ (and
hence point $p_i$) \emph{catches} $p_j$. Hence the term ``catch" in
the name \emph{proximity catch digraph}. If arcs of the form
$(p_j,p_j)$ (i.e., loops) were allowed, $D$ would have been called a
\emph{pseudodigraph} according to some authors (see, e.g.,
\cite{chartrand:1996}).

In a digraph $D=(\mathcal{V},\mathcal{A})$, a vertex $v \in \mathcal{V}$ \emph{dominates}
itself and all vertices of the form $\{u: (v,u) \in \mathcal{A}\}$. A
\emph{dominating set} $S_D$ for the digraph $D$ is a subset of
$\mathcal{V}$ such that each vertex $v \in \mathcal{V}$ is dominated by a vertex in
$S_D$. A \emph{minimum dominating set} $S^*_{D}$ is a dominating
set of minimum cardinality and the \emph{domination number}
$\gamma(D)$ is defined as $\gamma(D):=|S^*_{D}|$ (see, e.g., \cite{lee:1998}) where
$|\cdot|$ denotes the set cardinality functional. See
\cite{chartrand:1996} and \cite{west:2001} for more on graphs and digraphs.
If a minimum dominating set is of size one, we call it a \emph{dominating point}.

Note that for $|\mathcal{V}|=n>0$, $1 \le \gamma(D) \le n$, since $\mathcal{V}$ itself is always
a dominating set.

In recent years, a new classification tool based on the relative allocation of points
from various classes has been developed.
\cite{priebe:2001} introduced the \emph{class cover catch digraphs}
(CCCDs) and gave the exact and the asymptotic distribution
of the domination number of the CCCD
based on two sets, $\mathcal{X}_n$ and $\mathcal{Y}_m$, which are of size $n$ and
$m$, from classes, $\mathcal{X}$ and $\mathcal{Y}$, respectively,
and are sets of iid random variables from uniform
distribution on a compact interval in $\mathbb{R}$. \cite{devinney:2006},
\cite{devinney:2002a}, \cite{marchette:2003}, \cite{priebe:2003b, priebe:2003a}
applied the concept in higher dimensions and
demonstrated relatively good performance of CCCD in classification.
The methods employed involve \emph{data reduction (condensing)} by
using approximate minimum dominating sets as \emph{prototype sets}
(since finding the exact minimum dominating set is an NP-hard
problem in general
--- e.g., for CCCD in multiple dimensions --- (see \cite{devinney:2003}).
\cite{devinney:2002b} proved a SLLN result for the domination number
of CCCDs for one-dimensional data.
Although intuitively appealing and easy to extend to higher dimensions, exact
and asymptotic distribution of the domination number of the CCCDs
are not analytically tractable in $\mathbb{R}^2$ or higher dimensions.
As alternatives to CCCD, two new families of PCDs are introduced in
\cite{ceyhan:2003a, ceyhan:2005e} and are applied in
testing spatial point patterns (see, \cite{ceyhan:2005g, ceyhan:2006a}).
These new families are both applicable to pattern classification also.
They are designed to have better distributional and mathematical properties.
For example, the distribution of the relative density
(of arcs) is derived for one family in \cite{ceyhan:2005g} and for
the other family in \cite{ceyhan:2006a}.
In this article, we derive
the asymptotic distribution of the domination number of the latter
family called \emph{$r$-factor proportional-edge PCD}.
During the derivation process, we introduce auxiliary tools, such as,
\emph{proximity region} (which is the most crucial concept in defining
the PCD), \emph{$\Gamma_1$-region, superset region, closest edge
extrema, asymptotically accurate distribution,} and so on.
We utilize these special regions, extrema, and asymptotic expansion of the
distribution of these extrema.
The choice of the change of
variables in the asymptotic expansion is also dependent
on the type of the extrema used and
crucial in finding the limits of the improper integrals we encounter.
Our methodology is instructive in finding the distribution of the
domination number of similar PCDs in $\mathbb{R}^2$ or higher dimensions.

In addition to the mathematical tractability and applicability to
testing spatial patterns and classification, this new family of PCDs
is more flexible as it allows choosing an optimal parameter for best
performance in hypothesis testing or pattern classification.

The domination number of PCDs is first investigated for data in one
Delaunay triangle (in $\mathbb{R}^2$) and the analysis is generalized to
data in multiple Delaunay triangles. Some trivial proofs are
omitted, shorter proofs are given in the main body of the article;
while longer proofs are deferred to the Appendix.


\section{Proximity Maps and the Associated PCDs}

We construct the proximity regions using two data sets $\mathcal{X}_n$ and $\mathcal{Y}_m$
from two classes $\mathcal{X}$ and $\mathcal{Y}$, respectively.
Given $\mathcal{Y}_m \subseteq \Omega$, the {\em proximity map} $N_{\Y}(\cdot):
\Omega \rightarrow 2^{\Omega}$ associates a {\em proximity region}
$N_{\Y}(x) \subseteq \Omega$ with each point $x \in \Omega$.
The region $N_{\Y}(x)$ is defined in terms of the distance between $x$ and $\mathcal{Y}_m$.
More specifically, our $r$-factor proximity maps will be based on
the relative position of points from $\mathcal{X}_n$ with respect to the
Delaunay tessellation of $\mathcal{Y}_m$.
In this article, a triangle refers
to the closed region bounded by its edges.
See Figure \ref{fig:deltri} for an example with $n=200$ $\mathcal{X}$ points iid $\mathcal{U}
\bigl((0,1)\times (0,1)\bigr)$, the uniform distribution on the unit
square and the Delaunay triangulation is based on $m=10$ $\mathcal{Y}$
which are points also iid $\mathcal{U} \bigl((0,1)\times (0,1)\bigr)$.

\begin{figure}[ht]
\centering
 \rotatebox{-90}{ \resizebox{3. in}{!}{ \includegraphics{DelaunayXY.ps}}}
 \caption{ \label{fig:deltri}
A realization of $200$ $\mathcal{X}$ points (crosses) and the Delaunay
triangulation based on 10 $\mathcal{Y}$ points (circles). }
\end{figure}


If $\mathcal{X}_n=\bigl\{ X_1,\ldots,X_n \bigr\}$ is a set of $\Omega$-valued
random variables then $N_{\Y}(X_i)$ are random sets.
If $X_i$ are iid then so are the random sets $N_{\Y}(X_i)$.
We define the data-random proximity catch digraph $D$
--- associated with $N_{\Y}(\cdot)$ --- with vertex set
$\mathcal{X}_n=\{X_1,\cdots,X_n\}$ and arc set $\mathcal{A}$ by
 $$(X_i,X_j) \in \mathcal{A} \iff X_j \in N_{\Y}(X_i).$$
Since this relationship is not symmetric, a digraph is used rather than a graph.
The random digraph $D$ depends on the (joint)
distribution of $X_i$ and on the map $N_{\Y}(\cdot)$.
For $\mathcal{X}_n=\bigl\{ X_1,\cdots,X_n \bigr\}$, a set of iid random variables
from $F$, the domination number of the associated data-random
proximity catch digraph based on the proximity map $N(\cdot)$,
denoted $\gamma(\mathcal{X}_n,N)$, is the minimum number of point(s) that dominate
all points in $\mathcal{X}_n$.

The random variable $\gamma(\mathcal{X}_n,N)$ depends explicitly on $\mathcal{X}_n$ and $N(\cdot)$
and implicitly on $F$ .
Furthermore, in general, the
distribution, hence the expectation $\E[\gamma(\mathcal{X}_n,N)]$, depends on
$n$, $F$, and $N$; $ 1 \leq \E[\gamma(\mathcal{X}_n,N)] \le n.$
In general, the variance of $\gamma(\mathcal{X}_n,N)$ satisfies,
$1 \le \Var[\gamma(\mathcal{X}_n,N)] \le n^2/4$.

For example, the CCCD of \cite{priebe:2001} can be viewed as an
example of PCDs and is briefly discussed in the next section.
We use many of the properties of CCCD in $\mathbb{R}$ as guidelines in
defining PCDs in higher dimensions.

\subsection{Spherical Proximity Maps}
 Let $\mathcal{Y}_m=\left \{\mathsf{y}_1,\ldots,\mathsf{y}_m \right\} \subset \mathbb{R}$.
Then the proximity map associated with CCCD is defined as the open
ball $N_S(x):=B(x,r(x))$ for all $x \in \mathbb{R}$, where $r(x):=\min_{\mathsf{y}
\in \mathcal{Y}_m}d(x,\mathsf{y})$ (see \cite{priebe:2001}) with $d(x,y)$ being the
Euclidean distance between $x$ and $y$.
That is, there is an arc
from $X_i$ to $X_j$ iff there exists an open ball centered at $X_i$
which is ``pure" (or contains no elements) of $\mathcal{Y}_m$ in its
interior, and simultaneously contains (or ``catches") point $X_j$.
We consider the closed ball, $\overline{B}(x,r(x))$ for $N_S(x)$ in this article.
Then for $x \in \mathcal{Y}_m$, we have $N_S(x)=\{x\}$.
Notice that a
ball is a sphere in higher dimensions, hence the notation $N_S$.
Furthermore, dependence on $\mathcal{Y}_m$ is through $r(x)$.
Note that  in $\mathbb{R}$ this
proximity map is based on the intervals
$I_j=\left(\mathsf{y}_{(j-1):m},\mathsf{y}_{j:m} \right)$ for $j=0,\ldots,m+1$ with
$\mathsf{y}_{0:m}=-\infty$ and $\mathsf{y}_{(m+1):m}=\infty$, where $\mathsf{y}_{j:m}$ is the
$j^{th}$ order statistic in $\mathcal{Y}_m$. This interval partitioning can
be viewed as the Delaunay tessellation of $\mathbb{R}$ based on $\mathcal{Y}_m$. So
\emph{in higher dimensions, we use the Delaunay triangulation based
on $\mathcal{Y}_m$ to partition the support}.

A natural extension of the proximity region $N_S(x)$ to $\mathbb{R}^d$ with
$d>1$ is obtained as $N_S(x):=B(x,r(x))$ where
$r(x):=\min_{\mathsf{y} \in \mathcal{Y}_m} d(x,\mathsf{y})$ which
is called the \emph{spherical proximity map}.
The spherical proximity map $N_S(x)$ is well-defined for all $x \in \mathbb{R}^d$ provided
that $\mathcal{Y}_m \not= \emptyset$.
Extensions to $\mathbb{R}^2$ and higher
dimensions with the spherical proximity map --- with applications in
classification --- are investigated by  \cite{devinney:2006},
\cite{devinney:2002a}, \cite{marchette:2003}, \cite{priebe:2003b, priebe:2003a}.
However, finding the minimum dominating set
of CCCD (i.e., the PCD associated with $N_S(\cdot)$) is an NP-hard
problem and the distribution of the domination number is not
analytically tractable for $d>1$.
This drawback has motivated us to define
new types of proximity maps.
\cite{ceyhan:2005e} introduced $r$-factor proportional-edge PCD,
where the distribution
of the domination number of $r$-factor PCD with $r=3/2$ is used in
testing spatial patterns of segregation or association.
\cite{ceyhan:2006a} computed the asymptotic distribution of the
relative density of the $r$-factor PCD and used it for the same purpose.
\cite{ceyhan:2003a} introduced the central similarity
proximity maps and the associated PCDs, and \cite{ceyhan:2005g}
computed the asymptotic distribution of the relative density of the
parametrized version of the central similarity PCDs and applied the
method to testing spatial patterns. An extensive treatment of the
PCDs based on Delaunay tessellations is available in \cite{ceyhan:2004d}.

The following property (which is referred to as
\textbf{Property (\ref{prop:P6})}) of CCCDs in $\mathbb{R}$ plays an important role in
defining proximity maps in higher dimensions.
\begin{equation}
\label{prop:P6}
 \text{ \textbf{Property (1)} For $x \in I_j$, $N_S(x)$ is a proper subset
of $I_j$ for almost all $x \in I_j$.}
\end{equation}
In fact, \textbf{Property (\ref{prop:P6})} holds for all $x \in
I_j\setminus \{(\mathsf{y}_{(j-1):m}+\mathsf{y}_{j:m})/2\}$ for CCCDs in $\mathbb{R}$.
For $x \in I_j$, $N_S(x)=I_j$ iff
$x=\left(\mathsf{y}_{(j-1):m}+\mathsf{y}_{j:m} \right)/2$.
We define an associated region for such points in the general context.
The \emph{superset region} for any proximity map $N(\cdot)$ in
$\Omega$ is defined to be
$$\mathscr{R}_S(N):=\bigl\{ x \in \Omega: N(x) =\Omega \bigr\}.$$
For example, for $\Omega=I_j \subsetneq \mathbb{R}$,
$\mathscr{R}_S(N_S):=\{x \in I_j: N_S(x) = I_j\}=
\left\{ \left(\mathsf{y}_{(j-1):m}+\mathsf{y}_{j:m} \right)/2 \right\}$
and for $\Omega=\mathcal{T}_j \subsetneq \mathbb{R}^d$,
$\mathscr{R}_S(N_S):=\{x \in \mathcal{T}_j: N_S(x) = \mathcal{T}_j\},$
where $\mathcal{T}_j$ is the $j^{th}$ Delaunay cell in the Delaunay
tessellation. Note that for $x \in I_j$, $\lambda(N_S(x)) \le
\lambda(I_j)$ and $\lambda(N_S(x)) = \lambda(I_j)$ iff $x \in
\mathscr{R}_S(N_S)$ where $\lambda(\cdot)$ is the Lebesgue measure on $\mathbb{R}$. So
the proximity region of a point in $\mathscr{R}_S(N_S)$ has the largest Lebesgue measure.
Note also that given $\mathcal{Y}_m$, $\mathscr{R}_S(N_S)$ is
not a random set, but $\mathbf{I}(X\in \mathscr{R}_S(N_S))$ is a random variable,
where $\mathbf{I}(\cdot)$ stands for the indicator function.
\textbf{Property (\ref{prop:P6})} also implies that $\mathscr{R}_S(N_S)$ has
zero $\mathbb{R}$-Lebesgue measure.

Furthermore, given a set $B$ of size $n$ in $[\mathsf{y}_{1:m},\mathsf{y}_{m:m}] \setminus \mathcal{Y}_m$,
the number of disconnected components in the PCD based on $N_S(\cdot)$
is at least the cardinality of the set
$\{j \in \{1,2,\ldots,m\}: B \cap I_j \not=\emptyset \}$,
which is the set of indices of the intervals that contain
some point(s) from $B$.

Since the distribution of the domination number of spherical PCD
(or CCCD) is tractable in $\mathbb{R}$, but not in $\mathbb{R}^d$ with $d>1$, we try
to mimic its properties in $\mathbb{R}$ while defining new PCDs in higher
dimensions.

\section{The $r$-Factor Proportional-Edge Proximity Maps}
\label{sec:r-factor} First, we describe the construction of the
$r$-factor proximity maps and regions, then state some of its basic
properties and introduce some auxiliary tools.

\subsection{Construction of the Proximity Map}
Let $\mathcal{Y}_m=\left \{\mathsf{y}_1,\ldots,\mathsf{y}_m \right\}$ be $m$ points in
general position in $\mathbb{R}^d$ and $\mathcal{T}_j$ be the $j^{th}$ Delaunay cell
for $j=1,\ldots,J_m$, where $J_m$ is the number of Delaunay cells.
Let $\mathcal{X}_n$ be a set of iid random variables from distribution $F$ in
$\mathbb{R}^d$ with support $\mathcal{S}(F) \subseteq \mathcal{C}_H(\mathcal{Y}_m)$.

In particular, for illustrative purposes, we focus on $\mathbb{R}^2$ where
a Delaunay tessellation is a triangulation, provided that no more
than three points in $\mathcal{Y}_m$ are cocircular (i.e., lie in the same circle).
Furthermore, for simplicity,
let $\mathcal{Y}_3=\{\mathsf{y}_1,\mathsf{y}_2,\mathsf{y}_3\}$ be three non-collinear points
in $\mathbb{R}^2$ and $T(\Y_3)=T(\mathsf{y}_1,\mathsf{y}_2,\mathsf{y}_3)$ be the triangle
with vertices $\mathcal{Y}_3$.
Let $\mathcal{X}_n$ be a set of iid random variables from $F$ with
support $\mathcal{S}(F) \subseteq T(\Y_3)$.
If $F=\mathcal{U}(T(\Y_3))$, a composition of translation,
rotation, reflections, and scaling
will take any given triangle $T(\Y_3)$
to the basic triangle $T_b=T((0,0),(1,0),(c_1,c_2))$
with $0 < c_1 \le 1/2$, $c_2>0$,
and $(1-c_1)^2+c_2^2 \le 1$, preserving uniformity.
That is, if $X \sim \mathcal{U}(T(\Y_3))$ is transformed in the same manner to,
say $X'$, then we have $X' \sim \mathcal{U}(T_b)$.

For $r \in [1,\infty]$, define $N_{PE}^r(\cdot,M):=N(\cdot,M;r,\mathcal{Y}_3)$
to be the \emph{$r$-factor proportional-edge proximity map} with
$M$-vertex regions as follows (see also Figure \ref{fig:ProxMapDef1}
with $M=M_C$ and $r=2$).
For $x \in T(\Y_3) \setminus \mathcal{Y}_3$, let $v(x)
\in \mathcal{Y}_3$ be the vertex whose region contains $x$; i.e., $x \in
R_M(v(x))$. In this article \emph{$M$-vertex regions} are
constructed by the lines joining any point $M \in \mathbb{R}^2 \setminus
\mathcal{Y}_3$ to a point on each of the edges of $T(\Y_3)$. Preferably, $M$ is
selected to be in the interior of the triangle $T(\Y_3)^o$. For such an
$M$, the corresponding vertex regions can be defined using the line
segment joining $M$ to $e_j$, which lies on the line joining $\mathsf{y}_j$
to $M$; e.g. see Figure \ref{fig:vert-regions} (left) for vertex
regions based on center of mass $M_C$, and (right) incenter $M_I$.
With $M_C$, the lines joining $M$ and $\mathcal{Y}_3$ are the \emph{median
lines}, that cross edges at $M_j$ for $j=1,2,3$. $M$-vertex regions,
among many possibilities, can also be defined by the orthogonal
projections from $M$ to the edges. See \cite{ceyhan:2004d} for a
more general definition.
The vertex regions in Figure \ref{fig:ProxMapDef1} are
center of mass vertex regions or $CM$-vertex regions.
If $x$ falls on the boundary of two $M$-vertex regions,
we assign $v(x)$ arbitrarily.
Let $e(x)$ be the edge of $T(\Y_3)$ opposite of $v(x)$.
Let $\ell(v(x),x)$ be the line parallel to $e(x)$ through
$x$. Let $d(v(x),\ell(v(x),x))$ be the Euclidean (perpendicular)
distance from $v(x)$ to $\ell(v(x),x)$. For $r \in [1,\infty)$, let
$\ell_r(v(x),x)$ be the line parallel to $e(x)$ such that
$$
d(v(x),\ell_r(v(x),x)) = r\,d(v(x),\ell(v(x),x))\\
\text{ and }\\
d(\ell(v(x),x),\ell_r(v(x),x)) < d(v(x),\ell_r(v(x),x)).
$$
Let $T_r(x)$ be the triangle similar to and with the same
orientation as $T(\Y_3)$ having $v(x)$ as a vertex and $\ell_r(v(x),x)$
as the opposite edge. Then the {\emph r-factor proportional-edge
proximity region} $N_{PE}^r(x,M)$ is defined to be $T_r(x) \cap T(\Y_3)$.
Notice that $\ell(v(x),x)$ divides the edges of $T_r(x)$ (other than
the one lies on $\ell_r(v(x),x)$) proportionally with the factor
$r$. Hence the name \emph{$r$-factor proportional edge proximity
region}.

\begin{figure} [ht]
    \centering
   \scalebox{.35}{\input{Nofnu2.pstex_t}}
   \caption{Construction of $r$-factor proximity region,
$N_{PE}^{r=2}(x)$ (shaded region).} \label{fig:ProxMapDef1}
\end{figure}


\begin{figure}
\begin{center}
\psfrag{A}{\scriptsize{$\mathsf{y}_1$}}
 \psfrag{B}{\scriptsize{$\mathsf{y}_2$}}
\psfrag{C}{\scriptsize{$\mathsf{y}_3$}}
 \psfrag{CM}{\scriptsize{$M_C$}}
\psfrag{IC}{\scriptsize{$M_{I}$}}
 \psfrag{x}{}
 \psfrag{P1}{\scriptsize{$M_1$}}
 \psfrag{P2}{\scriptsize{$M_2$}}
 \psfrag{P3}{\scriptsize{$M_3$}}
\psfrag{R(A)}{\scriptsize{$R_{M_C}(A)$} }
\psfrag{R(B)}{\scriptsize{$R_{M_C}(B)$} }
\psfrag{R(C)}{\scriptsize{$R_{M_C}(C)$} }
 \epsfig{figure=AltCMVertexRegions.eps, height=140pt,width=200pt}
  \psfrag{1}{\scriptsize{$\mathsf{y}_2$}}
\psfrag{R(A)}{\scriptsize{$R_{M_I}(A)$} }
\psfrag{R(B)}{\scriptsize{$R_{M_I}(B)$} }
\psfrag{R(C)}{\scriptsize{$R_{M_I}(C)$} }
 \epsfig{figure=AltICVertexRegions.eps, height=140pt,width=200pt}
\end{center}
\caption{
 \label{fig:vert-regions}
The vertex regions constructed with center of mass $M_C$ (left) and
incenter $M_I$ (right) using the line segments on the line joining
$M$ to $\mathcal{Y}_3$. }
\end{figure}



Notice that $r \ge 1$ implies $x \in N_{PE}^r(x,M)$ for all $x \in T(\Y_3)$.
Furthermore,
$\lim_{r \rightarrow \infty} N_{PE}^r(x,M) = T(\Y_3)$ for all $x \in T(\Y_3) \setminus \mathcal{Y}_3$,
so we define $N_{PE}^{\infty}(x,M) = T(\Y_3)$ for all such $x$.
For $x \in \mathcal{Y}_3$, we define $N_{PE}^r(x,M) = \{x\}$ for all $r \in [1,\infty]$.


\begin{figure}[ht]
\centering
 \rotatebox{-90}{ \resizebox{2.1 in}{!}{\includegraphics{Pointsin1T.ps}}}
 \rotatebox{-90}{ \resizebox{2.1 in}{!}{\includegraphics{arcs_PE1T.ps}}}
 \caption{
 \label{fig:one-tri-arcs}
 A realization of 7 $\mathcal{X}$ points generated iid $\mathcal{U}(T(\Y_3))$ (left)
 and the corresponding arcs of $r$-factor proportional edge PCD with $r=3/2$ and $M=M_C$. }
\end{figure}

Hence, $r$-factor proportional edge PCD has vertices $\mathcal{X}_n$ and arcs
$(x_i,x_j)$ iff $x_j \in N_{PE}^r(x_i,M)$. See Figure
\ref{fig:one-tri-arcs} for a realization of $\mathcal{X}_n$ with $n=7$ and
$m=3$. The number of arcs is 12 and $\gamma_n(r=2,M_C)=1$.  By
construction, note that as $x$ gets closer to $M$ (or equivalently
further away from the vertices in vertex regions), $N_{PE}^r(x,M)$
increases in area, hence it is more likely for the outdegree of $x$
to increase.  So if more $\mathcal{X}$ points are around the center $M$, then
it is more likely for $\gamma_n$ to decrease, on the other hand, if more
$\mathcal{X}$ points are around the vertices $\mathcal{Y}_3$, then the regions get
smaller, hence it is more likely for the outdegree for such points
to be smaller, thereby implying $\gamma_n$ to increase.  This
probabilistic behaviour is utilized in \cite{ceyhan:2005e} for
testing spatial patterns.

Note also that, $N_{PE}^r(x,M)$ is a \emph{homothetic transformation
(enlargement)} with $r \ge 1$ applied on the region
$N_{PE}^{r=1}(x,M)$. Furthermore, this transformation is also an
\emph{affine similarity transformation}.

\subsection{Some Basic Properties and Auxiliary Concepts}

First, notice that $X_i \stackrel{iid}{\sim} F$, with the additional
assumption that the non-degenerate two-dimensional probability
density function $f$ exists with support $\mathcal{S}(F) \subseteq T(\Y_3)$,
imply that the special case in the construction of $N_{PE}^r$ ---
$X$ falls on the boundary of two vertex regions --- occurs with
probability zero. Note that for such an $F$, $N_{PE}^r(X)$ is a
triangle a.s.


The similarity ratio of $N_{PE}^r(x,M)$ to $T(\Y_3)$ is given by
$\frac{\min \Bigl(d\bigl(v(x),\,e(x)\bigr),r\,d\bigl(v(x),\,
\ell(v(x),x)\bigr)\Bigr)} {d(v(x),\,e(x))},$
 that is, $N_{PE}^r(x,M)$ is similar to $T(\Y_3)$ with
the above ratio. \textbf{Property (\ref{prop:P6})} holds depending
on the pair $M$ and $r$. That is, there exists an $r_0$ and a
corresponding point $M(r_0) \in T(\Y_3)^o$ so that $N_{PE}^{r_0}(x,M)$
satisfies \textbf{Property (\ref{prop:P6})} for all $r \le r_0$,
but fails to satisfy it otherwise. \textbf{Property (\ref{prop:P6})}
fails for all $M$ when $r=\infty$. With $CM$-vertex regions, for all
$r \in [1,\infty]$, the area $A\left(N_{PE}^r(x,M_C) \right)$ is a
continuous function of $d(\ell_r(v(x),x),v(x))$ which is a
continuous function of $d(\ell(v(x),x),v(x))$ which is a continuous
function of $x$.



Note that if $x$ is close enough to $M$,
we might have $N_{PE}^r(x,M) = T(\Y_3)$ for $r=\sqrt{2}$ also.

In $T(\Y_3)$, drawing the lines $q_j(r,x)$ such that
$d(\mathsf{y}_j,e_j)=r\,d(\mathsf{y}_j,q_j(r,x))$ for $j\in \{1,2,3\}$  yields a
triangle, denoted $\mathscr T_r$, for $r<3/2$ . See Figure
\ref{fig:Tr-RS-NDA-CC} for $\mathscr T_r$ with $r=\sqrt{2}$.


\begin{figure}
\begin{center}
\psfrag{A}{\scriptsize{$\mathsf{y}_1$}}
 \psfrag{B}{\scriptsize{$\mathsf{y}_2$}}
\psfrag{C}{\scriptsize{$\mathsf{y}_3$}}
 \psfrag{CC}{\scriptsize{$M_{CC}$}}
\psfrag{IC}{\scriptsize{$M_{I}$}}
 \psfrag{x}{\scriptsize{$x$}}
\psfrag{D}{}
 \psfrag{E}{}
 \psfrag{F}{}
\psfrag{S}{}
 \psfrag{Ac}{\scriptsize{$q_1(r,x)$} }
  \psfrag{Ab}{}
  \psfrag{Ba}{}
\psfrag{Bc}{\scriptsize{$q_2(r,x)$} }
 \psfrag{Ca}{}
\psfrag{Cb}{\scriptsize{$q_3(r,x)$} }
 \epsfig{figure=eqartriangle.eps, height=140pt , width=200pt}
\end{center}
\caption{The triangle $\mathscr T_r$ with $r=\sqrt{2}$ (the hatched region).
} \label{fig:Tr-RS-NDA-CC}
\end{figure}

The functional form of $\mathscr T_r$ in the basic triangle $T_b$ is given by
{\small
\begin{align}
\label{eqn:T^r-def}
& \mathscr T_r =T(t_1(r),t_2(r),t_3(r))= \left \{(x,y) \in T_b:
y \ge \frac{c_2\,(r-1)}{r};\; y \le \frac{c_2\,(1-r\,x)}{r\,(1-c_1)};\;
y \le \frac{c_2\,(r\,(x-1)+1)}{r\,c_1} \right\}\\
&=T\Biggl( \left(\frac{(r-1)\,(1+c_1)}{r},\frac{c_2\,(r-1)}{r} \right),
\left(\frac{2-r+c_1\,(r-1)}{r},\frac{c_2\,(r-1)}{r} \right),
\left(\frac{c_1\,(2-r)+r-1}{r},\frac{c_2\,(r-2)}{r} \right) \Biggr) \nonumber.
\end{align}
}
There is a crucial difference between the triangles $\mathscr T_r$ and $T(M_1,M_2,M_3)$.
More specifically $T(M_1,M_2,M_3) \subseteq \mathscr{R}_S(r,M)$ for all $M$ and $r \ge 2$, but
$(\mathscr T_r)^o$ and $\mathscr{R}_S(r,M)$ are disjoint for all $M$ and $r$. So if $M
\in (\mathscr T_r)^o$, then $\mathscr{R}_S(r,M)=\emptyset$; if $M \in
\partial(\mathscr T_r)$, then $\mathscr{R}_S(r,M)=\{M\}$; and if $M \not\in \mathscr T_r$,
then $\mathscr{R}_S(r,M)$ has positive area. Thus $N_{PE}^r(\cdot,M)$ fails to
satisfy \textbf{Property (\ref{prop:P6})} if $M \not\in \mathscr T_r$. See
Figure \ref{fig:SS-regions} for two examples of superset regions
with $M$ that corresponds to circumcenter $M_{CC}$ in this triangle
and the vertex regions are constructed using orthogonal projections.
For $r=2$, note that $\mathscr T_r=\emptyset$ and the superset region is
$T(M_1,M_2,M_3)$ (see Figure \ref{fig:SS-regions} (left)), while for
$r=\sqrt{2}$, $\mathscr T_r^o$ and $\mathscr{R}_S(r=\sqrt{2},M)^o$ are disjoint (see
Figure \ref{fig:SS-regions} (right))

The triangle $\mathscr T_r$ given in Equation (\ref{eqn:T^r-def}) and the
superset region $\mathscr{R}_S(r,M)$ play a crucial role in computing the
distribution of the domination number of the $r$-factor PCD.


\begin{figure}
\begin{center}
\psfrag{A}{\scriptsize{$\mathsf{y}_1$}}
 \psfrag{B}{\scriptsize{$\mathsf{y}_2$}}
\psfrag{C}{\scriptsize{$\mathsf{y}_3$}}
 \psfrag{CC}{\scriptsize{$M_{CC}$}}
 \psfrag{x}{}
 \psfrag{y}{}
  \psfrag{M1}{}
 \psfrag{M2}{}
 \psfrag{M3}{}
 \epsfig{figure=superseteqedgeCC.eps, height=140pt,width=200pt}
 \epsfig{figure=superseteqarCC.eps, height=140pt,width=200pt}
\end{center}
\caption{
 \label{fig:SS-regions}
The superset regions (the shaded regions) constructed with
circumcenter $M_{CC}$ with $r=\sqrt{2}$ (left) and $r=2$ (right)
with vertex regions constructed with orthogonal projections to the
edges. }
\end{figure}


\subsection{Main Result}
Next, we present the main result of this article. Let
$\gamma_n(r,M):=\gamma\left(\mathcal{X}_n, N_{PE}^r,M \right)$ be the domination number
of the PCD based on $N_{PE}^r$ with $\mathcal{X}_n$, a set of iid random
variables from $\U(T(\Y_3))$, with $M$-vertex regions.

The domination number $\gamma_n(r,M)$ of the PCD has the following
asymptotic distribution. As $n \rightarrow \infty$,
\begin{equation}
\label{eqn:asymptotic-NYr}
 \gamma_n(r,M) \sim
\left\lbrace \begin{array}{ll}
       2+\BER(1-p_r),           & \text{for $r \in [1,3/2]$ and $M \in \{t_1(r),t_2(r),t_3(r)\}$,}\\
       1,           & \text{for $r>3/2$,}\\
       3,           & \text{for $r \in [1,3/2)$ and $M \in \mathscr T_r\setminus \{t_1(r),t_2(r),t_3(r)\}$,}\\
\end{array} \right.
\end{equation}
where $\BER(p)$ stands for Bernoulli distribution with probability of
success $p$, $\mathscr T_r$ and $t_j(r)$ are defined in Equation
(\ref{eqn:T^r-def}), and for $r \in [1,3/2)$ and $M \in
\{t_1(r),t_2(r),t_3(r)\}$,
\begin{equation}
\label{eqn:p_r-form} p_r=\int_0^{\infty}\int_0^{\infty}\frac
{64\,r^2}{9\,(r-1)^2}\,w_1\,w_3\,\exp\left(\frac{4\,r}
{3\,(r-1)}\,(w_1^2+w_3^2+2\,r\,(r-1)\,w_1\,w_3)\right)\,dw_3w_1;
\end{equation}
for example for $r=3/2$ and $M=M_C$, $p_r \approx .7413$.

In Equation (\ref{eqn:asymptotic-NYr}), the first line is referred
as the non-degenerate case, the second and third lines are referred
as degenerate cases with a.s. limits 1 and 3, respectively.

\begin{figure}
\begin{center}
\psfrag{r}{\scriptsize{$r$}} \psfrag{pr}{\scriptsize{$p_r$}}
\epsfig{figure=pglt2ofr.eps, height=150pt, width=220pt}
\end{center}
\caption{ Plotted is the probability $p_r=\lim_{n\rightarrow
\infty}P\left( \gamma_n(r,M)=2 \right)$ given in Equation
(\ref{eqn:p_r-form}) as a function of $r$ for $r \in [1,3/2)$ and $M
\in \{t_1(r),t_2(r),t_3(r)\}$.} \label{fig:pglt2ofr}
\end{figure}

In the following sections, we define a region associated with $\gamma=1$
case in general. Then we give finite sample and asymptotic upper
bounds for $\gamma_n(r,M)$. Then we derive the asymptotic distribution
of $\gamma_n(r,M)$.


\section{The $\Gamma_1$-Regions for $N_{PE}^r$}
\label{sec:Gamma1-NYr}
First, we define $\Gamma_1$-regions in general,
and describe the
construction of $\Gamma_1$-region of $N_{PE}^r$ for one point and
multiple point data sets, and provide some results concerning $\Gamma_1$-regions.

\subsection{Definition of $\Gamma_1$-Regions}
Let $(\Omega,\mathcal{M})$ be a measurable space and consider the
proximity map $N:\Omega \rightarrow 2^{\Omega}$. For any set $B
\subseteq \Omega$, the \emph{$\Gamma_1$-region} of $B$ associated with
$N(\cdot)$, is defined to be the region $\Gamma^N_1(B):=\{z \in \Omega:
B \subseteq  N(z)\}$. For $x \in \Omega$, we denote
$\Gamma^N_1\bigl(\{x\}\bigr)$ as $\Gamma^N_1(x)$.

If $\mathcal{X}_n=\bigl\{ X_1,X_2,\cdots,X_n \bigr\}$ is a set
of $\Omega$-valued random variables,
then $\Gamma^N_1(X_i)$, $i=1,\cdots,n$, and $\Gamma^N_1(\mathcal{X}_n)$ are random sets.
If the $X_i$ are iid,
then so are the random sets $\Gamma^N_1(X_i)$.

 Note that $\gamma(\mathcal{X}_n,N)=1$ iff $\mathcal{X}_n \cap \Gamma^N_1(\mathcal{X}_n)\not= \emptyset$.
Hence the name \emph{$\Gamma_1$-region}.

It is trivial to see the following.
\begin{proposition}
\label{prop:RSsubsetG1}
For any proximity map $N$ and set $B \subseteq \Omega$, $\mathscr{R}_S(N) \subseteq \Gamma^N_1(B)$.
\end{proposition}


\begin{lemma}
\label{lem:gamma1-intersect} For any proximity map $N$ and $B
\subseteq \Omega$, $\Gamma^N_1(B)= \cap_{x \in B}\Gamma^N_1(x)$.
\end{lemma}
{\bfseries Proof:}  Given a particular type of proximity map $N$ and
subset $B \subseteq \Omega$, $y \in \Gamma^N_1(B)$ iff $B \subseteq
N(y)$ iff $x \in N(y)$ for all $x \in B$ iff $y \in \Gamma^N_1(x)$ for
all $x \in B$ iff $y \in \cap_{x \in B}\Gamma^N_1(x)$. Hence the result
follows. $\blacksquare$


A problem of interest is finding, if possible, a (proper) subset of
$B$, say $G \subsetneq B$, such that $\Gamma^N_1(B)=\cap_{x \in
G}\Gamma^N_1(x)$. This implies that only the points in $G$ will be
\emph{active} in determining $\Gamma^N_1(B)$.



For example, in $\mathbb{R}$ with $\mathcal{Y}_2=\{0,1\}$, and $\mathcal{X}_n$ a set of iid random variables of size $n>1$ from
$F$ in $(0,1)$,
 $\Gamma^{N_S}_1(\mathcal{X}_n)=\Bigl(X_{n:n}/2,(1+X_{1:n})/2 \Bigr)$.
So the extrema (minimum and maximum) of the set
$\mathcal{X}_n$ are sufficient to determine the $\Gamma_1$-region;
i.e., $G=\{X_{1:n},X_{n:n} \}$
for $\mathcal{X}_n$ a set of iid random variables from a continuous distribution on $(0,1)$.
Unfortunately, in the multi-dimensional case, there is no natural ordering that
yields natural extrema such as minimum or maximum.

\subsection{Construction of $\Gamma_1$-Region of a Point for $N_{PE}^r$}
For $N_{PE}^r(\cdot,M)$, the $\Gamma_1$-region,
denoted as $\Gamma^r_1(\cdot,M):=\Gamma^{N_{PE}^r}_1(\cdot,M)$, is constructed as follows;
see also Figure \ref{fig:ProxMapDef2}.
Let $\xi_j(r,x)$ be the line
parallel to $e_j$ such that $\xi_j(r,x)\cap T(\Y_3) \not=\emptyset$ and
$r\,d(\mathsf{y}_j,\xi_j(r,x))=d(\mathsf{y}_j,\ell(\mathsf{y}_j,x))$ for $j\in \{1,2,3\}$.
Then
$$\Gamma^r_1(x,M)=\cup_{j=1}^3 \bigl[ \Gamma^r_1(x,M)\cap R_M(\mathsf{y}_j)\bigr]$$
where
$\Gamma^r_1(x,M)\cap R_M(\mathsf{y}_j)=\{z \in R_M(\mathsf{y}_j):
d(\mathsf{y}_j,\ell(\mathsf{y}_j,z)) \ge d(\mathsf{y}_j,\xi_j(r,x)\} \text{ for } j\in
\{1,2,3\}.$

Notice that $r \ge 1$ implies that $x \in \Gamma^r_1(x,M)$.
Furthermore, $\lim_{r \rightarrow \infty} \Gamma^r_1(x,M) = T(\Y_3)$ for all
$x \in T(\Y_3) \setminus \mathcal{Y}_3$ and so we define $\Gamma^{r=\infty}_1(x,M) =
T(\Y_3)$ for all such $x$. For $x \in \mathcal{Y}_3$, $\Gamma^r_1(x,M)= \{x\}$ for
all $r \in [1,\infty]$.

\begin{figure} [ht]
    \centering
    \scalebox{.35}{\input{Gammaofnu.pstex_t}}
    \caption{Construction of the $\Gamma_1$-region, $\Gamma^{r=2}_1(x,M_C)$ (shaded region). }
\label{fig:ProxMapDef2}
\end{figure}

Notice that $\Gamma^r_1(x,M_C)$ is a convex hexagon for all $r \ge 2$
and $x \in T(\Y_3)\setminus \mathcal{Y}_3$, (since for such an $x$,
$\Gamma^r_1(x,M_C)$ is bounded by $\xi_j(r,x)$ and $e_j$ for all $j \in
\{1,2,3\}$, see also Figure \ref{fig:ProxMapDef2},) else it is
either a \emph{convex hexagon} or a \emph{non-convex} but \emph{star-shaped
polygon} depending on the location of $x$ and the value of $r$.

\subsection{The $\Gamma_1$-Region of a Multiple Point Data Set for $N_{PE}^r$}
So far, we have described the $\Gamma_1$-region for a point in $x \in
T(\Y_3)$. For a set $\mathcal{X}_n$ of size $n$ in $T(\Y_3)$, the region
$\Gamma^r_1(\mathcal{X}_n,M)$ can be specified by the edge extrema only.
The (closest) \emph{edge extrema} of a set $B$ in $T(\Y_3)$ are the
points closest to the edges of $T(\Y_3)$, denoted $x_{e_j}$ for $j\in
\{1,2,3\}$; that is, $x_{e_j} \in \arginf_{x \in B}d(x,e_j)$.
Note that if $B=\mathcal{X}_n$ is a set of iid random variables of size $n$
from $F$ then the edge extrema, denoted $X_{e_j}(n)$, are random
variables. Below, we show that the edge extrema are the active
points in defining $\Gamma^r_1(\mathcal{X}_n,M)$.

\begin{proposition}
\label{prop:SMA-edge-extrema}
Let $B$ be any set of $n$ distinct points in $T(\Y_3)$.
For $r$-factor proportional-edge proximity maps with $M$-vertex regions,
$\Gamma^r_1\left(B,M \right)=\cap_{k=1}^3\,\Gamma^r_1\left(x_{e_k},M \right)$.
\end{proposition}
{\bfseries Proof:}
Given $B = \{x_1,\ldots,x_n\}$ in $T(\Y_3)$.
Note that
$$\Gamma^r_1(B,M) \cap R_M(\mathsf{y}_j)=\bigl[\cap_{i=1}^n\,\Gamma^r_1(x_i,M)\bigr]\cap R_M(\mathsf{y}_j),$$
but by definition  $x_{e_j} \in \argmax_{x\in B}d(\mathsf{y}_j,\xi_j(r,x))$,
so
 \begin{equation}
 \label{eqn:G1-in3}
 \Gamma^r_1(B,M) \cap
R_M(\mathsf{y}_j)=\Gamma^r_1(x_{e_j},M)\cap R_M(\mathsf{y}_j) \text{ for }j\in
\{1,2,3\}.
 \end{equation}
Furthermore, $\Gamma^r_1(B,M) = \cup_{j=1}^3 \bigl[ \Gamma^r_1(x_{e_j},M)
\cap R_M(\mathsf{y}_j) \bigr]$, and
 \begin{equation}
 \label{eqn:G1-each-in3}
 \Gamma^r_1(x_{e_j},M) \cap
R_M(\mathsf{y}_j)=\cap_{k=1}^3 \bigl[ \Gamma^r_1(x_{e_k},M) \cap R_M(\mathsf{y}_j)
\bigr] \text{ for }j\in \{1,2,3\}.
 \end{equation}
Combining these two results in Equations (\ref{eqn:G1-in3}) and (\ref{eqn:G1-each-in3}),
we obtain $\Gamma^r_1(B,M)=\cap_{k=1}^3\,\Gamma^r_1(x_{e_k},M)$. $\blacksquare$


\begin{figure}
\begin{center}
\psfrag{A}{}
 \psfrag{B}{}
\psfrag{C}{\scriptsize{$\mathsf{y}_3$}}
\psfrag{IC}{\scriptsize{$M_{I}$}}
 \psfrag{x}{}
 \psfrag{0}{\scriptsize{$\mathsf{y}_1$}}
 \psfrag{1}{\scriptsize{$\mathsf{y}_2$}}
\psfrag{x1}{\scriptsize{$x_{e_1}$} }
\psfrag{x2}{\scriptsize{$x_{e_2}$} }
\psfrag{x3}{\scriptsize{$x_{e_3}$} }
 \epsfig{figure=EmpGamma1eqedgeIC.eps, height=140pt,width=200pt}
\psfrag{(x1,y1)}{\scriptsize{$x_{e_1}$} }
\psfrag{(x2,y2)}{\scriptsize{$x_{e_2}$} }
\psfrag{(x3,y3)}{\scriptsize{$x_{e_3}$} }
\psfrag{CC}{\scriptsize{$M_{CC}$}}
 \epsfig{figure=EmpGamma1eqedgeCC.eps, height=140pt,width=200pt}
\end{center}
\caption{
 \label{fig:G1-regions-n>1}
The $\Gamma_1$-regions (the hatched regions) for $r=2$ with seven $\mathcal{X}$ points
iid $\mathcal{U}(T(\Y_3))$ where vertex regions constructed with incenter $M_I$
(left) and circumcenter $M_{CC}$ (right) with orthogonal projection.
}
\end{figure}


From the above proposition, we see that the $\Gamma_1$-region for $B$ as
in proposition can also be written as the union of three regions of
the form
$$\Gamma^r_1(B,M)\cap R_M(\mathsf{y}_j)=\{z \in R_M(\mathsf{y}_j):\;
d(\mathsf{y}_j, \ell(\mathsf{y}_j,z)) \ge d(\mathsf{y}_j,\xi_j(r,x_{e_j}))\} \text{ for } j\in \{1,2,3\}.$$

See Figure \ref{fig:G1-regions-n>1} for $\Gamma_1$-region for $r=2$ with
seven $\mathcal{X}$ points iid $\mathcal{U}(T(\Y_3))$.
In the left figure, vertex regions are
based on incenter, while in the right figure, on circumcenter with
orthogonal projections to the edges. In either case $\mathcal{X}_n \cap
\Gamma^{r=2}_1(\mathcal{X}_n,M)$ is nonempty, hence $\gamma_n(2,M)=1$.

Below, we demonstrate that
edge extrema are distinct with probability 1 as $n \rightarrow
\infty$. Hence in the limit three distinct points suffice to determine
the $\Gamma_1$-region.
\begin{theorem}
\label{thm:distinct-edge-ext}
Let $\mathcal{X}_n$ be a set of iid random variables from $\U(T(\Y_3))$ and
let $E_{c,3}(n)$ be the event that (closest) edge extrema are distinct.
Then $P(E_{c,3}(n)) \rightarrow 1$ as $n \rightarrow \infty$.
\end{theorem}

We can also define the regions associated with $\gamma(\mathcal{X}_n,N)=k$ for $k
\le n$ called \emph{$\Gamma_k$-region} for proximity map
$N_{\mathcal{Y}_3}(\cdot)$ and set $B \subseteq \Omega$ for $k=1,\ldots,n$
(see \cite{ceyhan:2004d}).


\section{The Asymptotic Distribution of $\gamma_n(r,M)$}
\label{sec:asy-gam-NYr} In this section, we first present a finite
sample upper bound for $\gamma_n(r,M)$, then present the degenerate
cases, and the nondegenerate case of the asymptotic distribution of
$\gamma_n(r,M)$ given in Equation (\ref{eqn:asymptotic-NYr}).

\subsection{An Upper Bound for $\gamma_n(r,M)$}
 Recall that by definition, $\gamma(\mathcal{X}_n,N) \le
n$. We will seek an a.s. least upper bound for $\gamma(\mathcal{X}_n,N)$. Let
$\mathcal{X}_n$ be a set of iid random variables from $F$ on $T(\Y_3)$ and let
$\gamma(\mathcal{X}_n,N)$ be the domination number for the PCD based on a
proximity map $N$. Denote the general a.s. least upper bound for
$\gamma(\mathcal{X}_n,N)$ that works for all $n \ge 1$ and is independent of $n$
(which is called \emph{$\kappa$-value} in \cite{ceyhan:2004d}) as
$\kappa(N) := \min \{k: \gamma(\mathcal{X}_n, N) \le k \text{ a.s. for all } n
\ge 1\}$.

In $\mathbb{R}$ with $\mathcal{Y}_2=\{0,1\}$, for $\mathcal{X}_n$ a set of iid random variables from $\mathcal{U}(0,1)$,
$\gamma(\mathcal{X}_n,N_S) \le 2$ with equality holding with positive probability.
Hence $\kappa(N_S)=2$.

\begin{theorem}
\label{thm:kappaNYr=3}
Let $\mathcal{X}_n$ be a set of iid random variables from $\U(T(\Y_3))$ and $M \in \mathbb{R}^2 \setminus \mathcal{Y}_3$.
Then $\kappa\left(N_{PE}^r \right)=3$ for $N_{PE}^r(\cdot,M)$.
\end{theorem}
{\bfseries Proof:}
For $N_{PE}^r(\cdot,M)$, pick the point closest to edge $e_j$
in vertex region $R_M(\mathsf{y}_j)$;
that is, pick
$U_j \in \argmin_{X \in \mathcal{X}_n \cap R_M(\mathsf{y}_j)} d(X,e_j)
=\argmax_{X \in \mathcal{X}_n \cap R_M(\mathsf{y}_j)} d(\ell(\mathsf{y},X),\mathsf{y}_j)$
in the vertex region for which $X_n \cap R_M(\mathsf{y}_j) \not=\emptyset$
for $j \in \{1,2,3\}$ (note that as $n \rightarrow \infty$,
$U_j$ is unique a.s. for each $j$,
since $X$ is from $\U(T(\Y_3))$).
Then $\mathcal{X}_n \cap R_M(\mathsf{y}_j) \subset N_{PE}^r(U_j,M)$.
Hence $\mathcal{X}_n \subset \cup_{j=1}^3 N_{PE}^r(U_j,M)$.
 So $\gamma_n(r,M_C) \le 3$ with equality holding with positive probability.
Thus $\kappa\left(N_{PE}^r \right)=3$.
$\blacksquare$

Below is a general result for the limiting distribution of
$\gamma(\mathcal{X}_n,N)$ for $\mathcal{X}_n$ from a very broad family of distributions
and for general $N(\cdot)$.

\begin{lemma}
\label{lem:RS-nonempty} Let $\mathscr{R}_S(N)$ be the superset region for the
proximity map $N(\cdot)$ and $\mathcal{X}_n$ be a set of iid random variables
from $F$ with $P_F(X \in \mathscr{R}_S(N))>0$. Then $\lim_{n \rightarrow
\infty}P_F(\gamma(\mathcal{X}_n,N)=1)=1$.
\end{lemma}
{\bfseries Proof:}
Suppose $P_F(X \in \mathscr{R}_S(N))>0$.
Recall that for any $x \in \mathscr{R}_S(N)$, we have $N(x) = \Omega$,
so $\mathcal{X}_n \subseteq N(x)$, hence if $\mathcal{X}_n \cap \mathscr{R}_S(N) \not= \emptyset$
then $\gamma(\mathcal{X}_n,N)=1$.
Then $P(\mathcal{X}_n \cap \mathscr{R}_S(N)\not= \emptyset) \le P(\gamma(\mathcal{X}_n,N)=1)$.
But
$P\bigl(\mathcal{X}_n \cap \mathscr{R}_S(N)\not= \emptyset \bigr)=
1-P\bigl( \mathcal{X}_n \cap \mathscr{R}_S(N)=\emptyset \bigr)=
1-\bigl[1-P_F\bigl(X \in \mathscr{R}_S(N)\bigr)\bigr]^n
\rightarrow 1 \text{ as }n \rightarrow \infty,$
since $P_F\bigl(X \in \mathscr{R}_S(N)\bigr)>0$.
Hence $\lim_{n \rightarrow \infty}P(\gamma(\mathcal{X}_n,N)=1) =1$.
$\blacksquare$

\begin{remark}
\label{rem:rate-of-convergence}
In particular, for $F=\U(T(\Y_3))$,
the inequality $P_F(X \in \mathscr{R}_S(N))>0$ holds iff $A(\mathscr{R}_S(N))>0$,
then $P(\mathcal{X}_n \cap \mathscr{R}_S(N)\not= \emptyset)\rightarrow 1$. $\square$
\end{remark}
For $\mathcal{Y}_2=\{0,1\} \subset \mathbb{R}$, $\mathscr{R}_S(N_S)=\{1/2\}$, so Lemma
\ref{lem:RS-nonempty} does not apply to $N_S$ in $\mathbb{R}$.

Recall that $\kappa\left( N_{PE}^r \right) = 3$, then
$$1 \le \E\left[ \gamma_n(r,M) \right] \le 3 \text{    and    } 0 \le \Var\left[ \gamma_n(r,M) \right] \le 9/4.$$

Furthermore, there is a stochastic ordering for $\gamma_n(r,M)$.

\begin{theorem}
\label{thm:stochastic-r1<r2} Suppose $\mathcal{X}_n$ is a set of iid random
variables from a continuous distribution $F$ on $T(\Y_3)$. Then for
$r_1<r_2$, we have $\gamma_n(r_2,M) \le^{ST} \gamma\left(\mathcal{X}_n, N_{PE}^{r_1},M
\right)$.
\end{theorem}

{\bfseries Proof:}
Suppose $r_1<r_2$.
Then
$P\left(\gamma_n(r_2,M) \le 1\right)>P\left(\gamma_n(r_1,M)\le 1\right)$
since $\Gamma^{r_1}_1(\mathcal{X}_n,M) \subsetneq \Gamma^{r_2}_1(\mathcal{X}_n,M)$
for any realization of $\mathcal{X}_n$ and by a similar argument
$P\bigl(\gamma_n(r_2,M) \le 2\bigr)>P\left(\gamma_n(r_1,M) \le 2\right)$
so
$P\left(\gamma_n(r_2,M) \le 3\right) = P\left(\gamma_n(r_1,M) \le 3\right).$
Hence the desired result follows. $\blacksquare$

\subsection{Geometry Invariance}
We present a ``geometry invariance" result for $N_{PE}^r(\cdot,M)$
where $M$-vertex regions are constructed using the lines joining
$\mathcal{Y}_3$ to $M$, rather than the orthogonal projections from $M$ to
the edges. This invariance property will simplify the notation in
our subsequent analysis by allowing us to consider the special case
of the equilateral triangle.

\begin{theorem}
\label{thm:geo-inv-NYr} (Geometry Invariance Property)
Suppose $\mathcal{X}_n$ is a set of iid random variables from $\U(T(\Y_3))$.
Then for any $r \in [1,\infty]$ the distribution of $\gamma_n(r,M)$ is
independent of $\mathcal{Y}_3$ and hence the geometry of $T(\Y_3)$.
\end{theorem}

{\bfseries Proof:}
Suppose $X \sim \mathcal{U}(T(\mathcal{Y}))$.
A composition of translation, rotation,
reflections, and scaling will take any given triangle
$T(\mathcal{Y})=T(\mathsf{y}_1,\mathsf{y}_2,\mathsf{y}_3)$ to the basic triangle
$T_b=T((0,0),(1,0),(c_1,c_2))$ with $0 < c_1 \le 1/2$, $c_2>0$, and
$(1-c_1)^2+c_2^2 \le 1$.
Furthermore, when $X$ is also transformed in the same manner, say to $X'$,
then $X'$ is uniform on $T_b$, i.e., $X' \sim \mathcal U(T_b)$.
The transformation
$\phi_e:\mathbb{R}^2 \rightarrow \mathbb{R}^2$ given by $\phi_e(u,v)=\left(
u+\frac{1-2\,c_1}{\sqrt{3}}\,v, \frac{\sqrt{3}}{2\,c_2}\,v \right)$
takes $T_b$ to the equilateral triangle
$T_e=\bigl((0,0),(1,0),(1/2,\sqrt{3}/2)\bigr)$.
Investigation of the
Jacobian shows that $\phi_e$ also preserves uniformity.
That
is, $\phi_e(X') \sim \mathcal U(T_e)$.
Furthermore,
the composition of $\phi_e$, with the scaling and rigid body
transformations, maps
     the boundary of the original triangle, $T_o$,
  to the boundary of the equilateral triangle, $T_e$,
     the lines joining $M$ to $\mathsf{y}_j$ in $T_b$
  to the lines joining $\phi_e(M)$ to $\phi_e(\mathsf{y}_j)$ in $T_e$,
and  lines parallel to the edges of $T_o$
  to lines parallel to the edges of $T_e$.
Since the distribution of $\gamma_n(r,M)$ involves only probability
content of unions and intersections of regions bounded by precisely
such lines and the probability content of such regions is preserved
since uniformity is preserved; the desired result follows.
$\blacksquare$

Note that geometry invariance of $\gamma\left(\mathcal{X}_n, N_{PE}^{r=\infty},M
\right)$ also follows trivially, since for $r=\infty$,
we have $\gamma_n(r=\infty,M)=1$ a.s. for all $\mathcal{X}_n$ from any $F$ with support
in $T(\Y_3) \setminus \mathcal{Y}_3$.

Based on Theorem \ref{thm:geo-inv-NYr} we may assume that $T(\Y_3)$ is a
standard equilateral triangle with \\$\mathcal{Y}_3= \left\{ (0,0),(1,0),
\left( 1/2,\sqrt{3}/2 \right) \right\}$ for $N_{PE}^r(\cdot,M)$ with
$M$-vertex regions.

Notice that, we proved the geometry invariance property for $N_{PE}^r$
where $M$-vertex regions are defined with the lines joining $\mathcal{Y}_3$ to $M$.
On the other hand, if we use the orthogonal projections from
$M$ to the edges, the vertex regions, hence $N_{PE}^r$ will depend on
the geometry of the triangle.
That is, the orthogonal projections
from $M$ to the edges will not be mapped to the orthogonal
projections in the standard equilateral triangle.
Hence with the
choice of the former type of $M$-vertex regions, it suffices to work
on the standard equilateral triangle.
On the other hand, with the orthogonal projections, the exact and
asymptotic distribution of $\gamma_n$ will depend on $c_1,c_2$, so one
needs to do the calculations for each possible combination of
$c_1,c_2$.

\subsection{The Degenerate Case with $\gamma_n(r,M) \stackrel{p}{\rightarrow} 1$}

Below, we prove that $\gamma_n(r,M)$ is degenerate in the limit for
$r>3/2$.
\begin{theorem}
\label{thm:M-notin-Tr} Suppose $\mathcal{X}_n$ is a set of iid random
variables from a continuous distribution $F$ on $T(\Y_3)$. If $M \not\in
\mathscr T_r$ (see Figure \ref{fig:Tr-RS-NDA-CC} and Equation
(\ref{eqn:T^r-def}) for $\mathscr T_r$), then $\lim_{n \rightarrow
\infty}P\left( \gamma_n(r,M)=1 \right) =1$ for all $M \in \mathbb{R}^2 \setminus
\mathcal{Y}_3$.
\end{theorem}
{\bfseries Proof:} Suppose $M \notin \mathscr T_r$. Then $\mathscr{R}_S\left( N_{PE}^r,M
\right)$ is nonempty with positive area. Hence the result follows by
Lemma \ref{lem:RS-nonempty}. $\blacksquare$

\begin{corollary}
\label{cor:M-notin-Tr} Suppose $\mathcal{X}_n$ is a set of iid random
variables from a continuous distribution $F$ on $T(\Y_3)$. Then for
$r>3/2$,
 $\lim_{n \rightarrow \infty}P\left( \gamma_n(r,M)=1 \right) =1$
for all $M \in R^2\setminus \mathcal{Y}_3$.
\end{corollary}
{\bfseries Proof:}
For $r>3/2$,  $\mathscr T_r=\emptyset$, so $M \not\in \mathscr T_r$.
Hence the result follows by Theorem \ref{thm:M-notin-Tr}.
$\blacksquare$

We estimate the distribution of $\gamma_n(r,M)$ with $r=2$ and $M=M_C$
for various $n$ empirically. In Table
\ref{tab:numerical-gamma-NYr=2,5/4} (left), we present the empirical
estimates of $\gamma_n(r,M)$ with $n=10,\,20,\,30,\,50,\,100$ based on
$1000$ Monte Carlo replicates in $T_e$. Observe that the empirical
estimates are in agreement with the asymptotic distribution given in
Corollary \ref{cor:M-notin-Tr}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{cc}

\begin{tabular}{|c|c|c|c|c|c|}
\hline
$ k \diagdown n$  & 10 & 20 & 30 & 50 & 100\\
\hline
1 & 961 & 1000 & 1000 & 1000 & 1000 \\
\hline
2 & 34 & 0 & 0 & 0 & 0  \\
\hline
3 & 5 & 0 & 0 & 0 & 0 \\
\hline
\end{tabular}

&

\begin{tabular}{|c|c|c|c|c|c|}
\hline
$ k \diagdown n$  & 10 & 20 & 30 & 50 & 100\\
\hline
1 & 9 & 0 & 0 & 0 & 0 \\
\hline
2 & 293 & 110 & 30 & 8 & 0  \\
\hline
3 & 698 & 890 & 970 & 992 & 1000 \\
\hline
\end{tabular}

\end{tabular}
\end{center}
\caption{ \label{tab:numerical-gamma-NYr=2,5/4} The number of
$\gamma_n(r,M)=k$ out of $N=1000$ Monte Carlo replicates with $M=M_C$
and $r=2$ (left) and $r=5/4$ (right).}
\end{table}



The asymptotic distribution of $\gamma_n(r,M)$ for $r <3/2$ depends on
the relative position of $M$ with respect to the triangle $\mathscr T_r$.

\subsection{The Degenerate Case with $\gamma_n(r,M) \stackrel{p}{\rightarrow} 3$}

\begin{theorem}
\label{thm:gnNYr=3}
Suppose $\mathcal{X}_n$ is a set of iid random variables from a continuous distribution $F$
on $T(\Y_3)$.
If $M \in (\mathscr T_r)^o$, then $P\left( \gamma_n(r,M)=3 \right) \rightarrow 1$
as $n \rightarrow \infty$.
\end{theorem}

We estimate the distribution of $\gamma_n(r,M)$ with $r=5/4$ and $M=M_C$
for various $n$ values empirically. In Table
\ref{tab:numerical-gamma-NYr=2,5/4} (right), we present the
empirical estimates of $\gamma_n(r,M)$ with $n=10,\,20,\,30,\,50,\,100$
based on $1000$ Monte Carlo replicates in $T_e$. Observe that the
empirical estimates are in agreement with our result in Theorem
\ref{thm:gnNYr=3}.

\begin{theorem}
\label{thm:MinboundaryTr-g>1} Suppose $\mathcal{X}_n$ is a set of iid random
variables from $\U(T(\Y_3))$. If $M \in \partial(\mathscr T_r)$, then $P\left(
\gamma_n(r,M)>1 \right) \rightarrow 1$ as $n \rightarrow \infty$.
\end{theorem}


For $M \in \partial(\mathscr T_r)$, there are two separate cases:
\begin{itemize}
\item[(i)]
$M \in \partial(\mathscr T_r) \setminus \{t_1(r),\,t_2(r),\,t_3(r)\}$ where $t_j(r)$ with
$j \in \{1,2,3\}$ are the vertices of $\mathscr T_r$ whose explicit forms are
given in Equation (\ref{eqn:T^r-def}).
\item[(ii)]
$M \in \{t_1(r),\,t_2(r),\,t_3(r)\}$.
\end{itemize}

\begin{theorem}
\label{thm:g_nNYr=3-for-r<3/2}
Suppose $\mathcal{X}_n$ is a set of iid random variables from  $\U(T(\Y_3))$.
If $M \in \partial(\mathscr T_r)\setminus \{t_1(r),\,t_2(r),\,t_3(r)\}$, then
$P\left( \gamma_n(r,M)=3 \right) \rightarrow 1$ as $n \rightarrow
\infty$.
\end{theorem}


We estimate the distribution of $\gamma_n(r,M)$ with $r=5/4$ and
$M=\left( 3/5,\sqrt{3}/10\right)\in \partial(\mathscr T_r)\setminus
\{t_1(r),\,t_2(r),\,t_3(r)\}$ for various $n$ empirically. In Table
\ref{tab:numerical-gamma-NYr=5/4-1} we present empirical estimates
of $\gamma_n(r,M)$ with $n=10,\,20,\,30,\,50,\,100,\,500,\\
\,1000,\,2000$
based on $1000$ Monte Carlo replicates in $T_e$. Observe that the
empirical estimates are in agreement with our result in Theorem
\ref{thm:g_nNYr=3-for-r<3/2}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$ k \diagdown n$  & 10 & 20 & 30 & 50 & 100 & 500 & 1000 & 2000\\
\hline
1 & 118 & 60 & 51 & 39 & 15 & 1 & 2 & 1 \\
\hline
2 & 462 & 409 & 361 & 299 & 258 & 100 & 57 & 29  \\
\hline
3 & 420 & 531 & 588 & 662 & 727 & 899 & 941 & 970\\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:numerical-gamma-NYr=5/4-1} The number of
$\gamma_n(r,M)=k$ out of $N=1000$ Monte Carlo replicates with $r=5/4$
and $M=\left( 3/5,\sqrt{3}/10\right)$.}
\end{table}

\subsection{The Nondegenerate Case}

\begin{theorem}
\label{thm:g_nNYr=2-for-r-vertex-of-Tr}
Suppose $\mathcal{X}_n$ is a set of iid random variables from $\U(T(\Y_3))$.
If $M \in \{t_1(r),\,t_2(r),\,t_3(r)\}$, then $P\left( \gamma_n(r,M)=2
\right) \rightarrow p_r$ as $n \rightarrow \infty$ where $p_r \in (0,1)$ is
provided in Equation (\ref{eqn:p_r-form}) but only
numerically computable.
\end{theorem}

For example, $p_{r=5/4} \approx .6514$ and $p_{r=\sqrt{2}} \approx .4826$.

So the asymptotic distribution of $\gamma_n(r,M)$ with $r \in [1,3/2)$
and $M \in \{t_1(r),t_2(r),t_3(r)\}$ is given by
\begin{equation}
\label{eqn:Asydist-NYr} \gamma_n(r,M) \sim 2+\BER(1-p_r).
\end{equation}

We estimate the distribution of $\gamma_n(r,M)$ with $r=5/4$ and
$M=\left( 7/10,\sqrt{3}/10 \right)$ for various $n$ empirically. In
Table \ref{tab:numerical-gamma-NYr=5/4-2}, we present the empirical
estimates of $\gamma_n(r,M)$ with
$n=10,\,20,\,30,\,50,\,100,\,500,\,1000,\,2000$ based on $1000$
Monte Carlo replicates in $T_e$. Observe that the empirical
estimates are in agreement with our result $p_{r=5/4} \approx
.6514$.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$ k \diagdown n$  & 10 & 20 & 30 & 50 & 100 & 500 & 1000 & 2000\\
\hline
1 & 174 & 118 & 82 & 61 & 22 & 5 & 1 & 1\\
\hline
2 & 532 & 526 & 548 & 561 & 611 & 617 & 633 & 649  \\
\hline
3 & 294 & 356 & 370 & 378 & 367 & 378 & 366 & 350\\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:numerical-gamma-NYr=5/4-2} The number of
$\gamma_n(r,M)=k$ out of $N=1000$ Monte Carlo replicates with $r=5/4$
and $M=\left(7/10,\sqrt{3}/10 \right)$.}
\end{table}

\begin{remark}
For $r=3/2$, as $n \rightarrow \infty$, $P\left( \gamma_n(r,M_C)
> 1 \right) \rightarrow 1$ at rate $O\left( n^{-1} \right)$.
$\square$
\end{remark}


\begin{theorem}
\label{thm:asydist-gamma-NY3/2}
Suppose $\mathcal{X}_n$ is a set of iid random variables from $\U(T(\Y_3))$.
Then for $r=3/2$, as $n \rightarrow \infty$,
\begin{equation}
\label{eqn:Asydist-NY3/2} \gamma_n(3/2,M_C) \sim 2+\BER(p \approx .2487)
\end{equation}
\end{theorem}

For the proof of Theorem \ref{thm:asydist-gamma-NY3/2},
see \cite{ceyhan:2004e, ceyhan:2005e}.

Using Theorem \ref{thm:asydist-gamma-NY3/2},
\begin{equation}
\label{eqn:Asymom-NY3/2-1} \lim_{n \rightarrow \infty}\E\left[
\gamma_n(3/2,M_C) \right]= 3-p_{3/2} \approx 2.2587
\end{equation}
and
\begin{equation}
\label{eqn:Asymom-NY3/2-2} \lim_{n \rightarrow \infty}\Var\left[
\gamma_n(3/2,M_C) \right]= 6+p_{3/2}-p_{3/2}^2 \approx .1917.
\end{equation}
Indeed, the finite sample distribution of $\gamma_n(3/2,M_C)$ hence the
finite sample mean and variance can also be obtained by numerical
methods.

We also estimate the distribution of $\gamma_n(3/2,M_C)$ for various $n$
values empirically.
The empirical estimates for
$n=10,\,20,30,\,50,\,100,\,500,\,1000,\,2000$ based on $1000$ Monte
Carlo replicates are given in Table \ref{tab:numerical-gamma-NY3/2}.
estimates are in agreement with our result $p_{r=3/2} \approx
.7413$.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|}
\hline
$ k \diagdown n$  & 10 & 20 & 30 &  50 & 100 & 500 & 1000 & 2000\\
\hline
1  & 151 & 82 & 61 & 50 & 27 & 2 & 3 & 1\\
\hline
2 &  602 & 636 & 688 & 693 & 718 & 753  & 729 & 749\\
\hline
3  & 247 & 282 & 251 & 257 & 255 & 245 & 268 & 250 \\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:numerical-gamma-NY3/2} The number of
$\gamma_n(3/2,M_C)=k$ out of $N=1000$ Monte Carlo replicates.}
\end{table}


\subsection{Distribution of the $\gamma_n(r,M)$ in Multiple Triangles}
So far we have worked with data in one Delaunay triangle, i.e.,
$m=3$ or $J_3=1$. In this section, we present the asymptotic
distribution of the domination number of $r$-factor PCDs in multiple
Delaunay triangles. Suppose $\mathcal{Y}_m=\{\mathsf{y}_1,\mathsf{y}_2,\ldots,\mathsf{y}_m\} \subset
\mathbb{R}^2$ be a set of $m$ points in general position with $m>3$ and no
more than 3 points are cocircular. Then there are $J_m>1$ Delaunay
triangles each of which is denoted as $\mathcal{T}_j$. Let $M^j$ be the point
in $\mathcal{T}_j$ that corresponds to $M$ in $T_e$, $\mathscr T_r^j$ be the triangle
that corresponds to $\mathscr T_r$ in $T_e$, and $t_i^j(r)$ be the vertices
of $\mathscr T_r^j$ that correspond to $t_i(r)$ in $T_e$ for $i \in
\{1,2,3\}$. Moreover, let $n_j:=|\mathcal{X}_n \cap \mathcal{T}_j|$, the number of $X$
points in Delaunay triangle $\mathcal{T}_j$. For $\mathcal{X}_n \subset \mathcal{C}_H(\mathcal{Y}_m)$,
let $\gamma_{n_j}(r,M^j)$ be the domination number of the digraph
induced by vertices of $\mathcal{T}_j$ and $\mathcal{X}_n \cap \mathcal{T}_j$. Then the
domination number of the $r$-factor PCD in $J_m$ triangles is
$$\gamma_n(r,M,J_m)=\sum_{j=1}^{J_m}\gamma_{n_j}(r,M^j).$$
See Figure \ref{fig:multi-tri-arcs} (left) for the 77 $\mathcal{X}$ points
that are in $\mathcal{C}_H(\mathcal{Y}_m)$ out of the 200 $\mathcal{X}$ points plotted in
Figure \ref{fig:deltri}. Observe that 10 $\mathcal{Y}$ points yield
$J_{10}=13$ Delaunay triangles. In Figure \ref{fig:multi-tri-arcs}
(right) are the corresponding arcs for $M=M_C$ and $r=3/2$. The
corresponding $\gamma_n=22$. Suppose $\mathcal{X}_n$ is a set of iid random
variables from $\mathcal{U}(\mathcal{C}_H(\mathcal{Y}_m))$, the uniform distribution on convex
hull of $\mathcal{Y}_m$ and we construct the $r$-factor PCDs using the points
$M^j$ that correspond to $M$ in $T_e$. Then for fixed $m$ (or fixed
$J_m$), as $n \rightarrow \infty$, so does each $n_j$. Furthermore,
as $n \rightarrow \infty$, each component $\gamma_{n_j}(r,M^j)$ become
independent. Therefore using Equation (\ref{eqn:asymptotic-NYr}), we
can obtain the asymptotic distribution of $\gamma_n(r,M,J_m)$. As $n
\rightarrow \infty$, for fixed $J_m$,\\

\noindent
 \begin{equation}
 \label{eqn:asymptotic-NYr-Jm}
 \gamma_n(r,M,J_m) \sim
\left\lbrace
 \begin{array}{ll}
       2\,J_m+\BIN(J_m,1-p_r),           & \text{for $M^j \in \{t^j_1(r),t^j_2(r),t^j_3(r)\}$ and $r \in [1,3/2]$,}\\
       J_m,           & \text{for $r>3/2$,}\\
       3\,J_m,           & \text{for $M \in \mathscr T_r^j\setminus \{t^j_1(r),t^j_2(r),t^j_3(r)\}$ and $r \in [1,3/2)$,}\\

\end{array} \right.
\end{equation}
\noindent where $\BIN(n,p)$ stands for binomial distribution with
$n$ trials and probability of success $p$, for $r \in [1,3/2)$ and
$M \in \{t_1(r),t_2(r),t_3(r)\}$, $p_r$ is given in Equation
\ref{eqn:asymptotic-NYr} and for $r=3/2$ and $M=M_C$, $p_r \approx
.7413$ (see Equation (\ref{eqn:Asydist-NY3/2})).

\begin{figure}[ht]
\centering
 \rotatebox{-90}{ \resizebox{3. in}{!}{\includegraphics{DelaunayCH.ps}}}
 \rotatebox{-90}{ \resizebox{3. in}{!}{\includegraphics{arcs_PE.ps}}}
 \caption{
 \label{fig:multi-tri-arcs}
 The 77 $\mathcal{X}$ points (crosses) in the convex hull of $\mathcal{Y}$ points (circles)
 given in Figure \ref{fig:deltri} (left) and the corresponding arcs (right) of
 $r$-factor proportional edge PCD with $r=3/2$ and $M=M_C$. }
\end{figure}


\subsection{Extension of $N_{PE}^r$ to Higher Dimensions}
\label{sec:NYr-higher-D}
The extension to $\mathbb{R}^d$ for $d > 2$ with $M=M_C$ is provided in \cite{ceyhan:2005e},
but the extension for general $M$ is similar.

Let $\gamma_n(r,M,d):=\gamma(\mathcal{X}_n,N_{PE}^r,M,d)$ be the domination number of the PCD based on
the extension of $N_{PE}^r(\cdot,M)$ to $\mathbb{R}^d$. Then it is easy to
see that $\gamma_n(r,M,3)$ is nondegenerate as $n \rightarrow \infty$ for $r=4/3$.
In $\mathbb{R}^d$, it can be seen that
$\gamma_n(r,M,d)$ is nondegenerate in the limit only when $r=(d+1)/d$.
Furthermore, for large $d$, asymptotic distribution of
$\gamma_n(r,M,d)$ is nondegenerate at values of $r$ closer to $1$.
Moreover, it can be shown that
$\lim_{n \rightarrow \infty}P \bigl( 2 \le \gamma_n(r=(d+1)/d,M,d ) \le d+1\bigr)=1$
and we conjecture the following.

\begin{conjecture}
Suppose $\mathcal{X}_n$ is  set of iid random variables from the uniform
distribution on a simplex in $\mathbb{R}^d$. Then the domination number
$\gamma_n(r,M)$ in the simplex satisfies
$$\lim_{n \rightarrow \infty}P\left( d \le \gamma_n((d+1)/d,M,d) \le d+1 \right)=1.$$
\end{conjecture}

For instance, with  $d=3$ we estimate the empirical distribution of
$\gamma(\mathcal{X}_n,4/3)$ for various $n$. The empirical estimates for
$n=10,\,20,\,30,\,40,\,50,\,100,\,200,\,500,\,1000,\,2000$ based on $1000$
Monte Carlo replicates for each $n$ are given in
Table \ref{tab:numerical-gamma-NY4/3-in-R3}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|}
\hline
$ k \diagdown n$  & 10 & 20 & 30 & 40 & 50 & 100 & 200 & 500 & 1000 & 2000\\
\hline
1  & 52 &  18 &   5 &   5  &  4  &  0  &  0  &  0 &   0  &   0\\
\hline
2 &  385 & 308 & 263 & 221 & 219 & 155 & 88 &  41 &  31 &   19 \\
\hline
3  & 348 &  455 &  557 & 609 & 621 & 725 & 773 & 831 & 845 &  862\\
\hline
4  & 215 &  219 &  175 & 165 & 156 & 120 & 139 & 128 & 124 &  119\\
\hline
\end{tabular}
\end{center}
\caption{\label{tab:numerical-gamma-NY4/3-in-R3} The number of
$\gamma_n(4/3,M_C)=k$ out of $N=1000$ Monte Carlo replicates.}
\end{table}


\section{Discussion}
The $r$-factor proportional-edge proximity catch digraphs (PCDs),
when compared to class cover catch digraphs (CCCDs), have some advantages.
The asymptotic distribution of the domination number
$\gamma_n(r,M)$ of the $r$-factor PCDs, unlike that of CCCDs, is mathematically tractable
(computable by numerical integration).
A minimum dominating set can be found in
polynomial time for $r$-factor PCDs in $\mathbb{R}^d$ for all $d\ge 1$,
but finding a minimum
dominating set is an NP-hard problem for CCCDs (except for $\mathbb{R}$).
These nice properties of $r$-factor PCDs are due to the geometry invariance of
distribution of $\gamma_n(r,M)$ for uniform data in triangles.

On the other hand,
CCCDs are easily extendable to higher dimensions
and are defined for all $\mathcal{X}_n \subset \mathbb{R}^d$,
while $r$-factor PCDs are only defined for
$\mathcal{X}_n \subset \mathcal{C}_H(\mathcal{Y}_m)$.
Furthermore, the CCCDs based on balls use proximity regions
that are defined by the obvious metric, while the PCDs
in general do not suggest a metric.
In particular, our $r$-factor PCDs are based on some sort of dissimilarity measure,
but no metric underlying this measure exists.

The finite sample distribution of $\gamma_n(r,M)$, although
computationally tedious, can be found by numerical methods, while
that of CCCDs can only be empirically estimated by Monte Carlo simulations.
Moreover, we had to introduce many auxiliary tools to compute the distribution
of  $\gamma_n(r,M)$ in $\mathbb{R}^2$.
Same tools will work in higher dimensions,
perhaps with more complicated geometry.

The $r$-factor PCDs have applications in classification and testing
spatial patterns of segregation or association.
The former can be performed building discriminant regions for classification
in a manner analogous to the procedure proposed in \cite{priebe:2003b};
and the latter can be performed by using the asymptotic
distribution of $\gamma_n(r,M)$ similar to the procedure used in \cite{ceyhan:2005e}.

\section*{Acknowledgements}
This work was partially by the
Defense Advanced Research Projects Agency
as administered by the Air Force Office of Scientific Research
under contract DOD F49620-99-1-0213 and by
Office of Naval Research Grant N00014-95-1-0777.
We also thank anonymous referees, whose constructive comments and
suggestions greatly improved the presentation and flow of this article.


