VS4 - Extrema in Delaunay Cells

2023-12-18

First we load the pcds package:

library(pcds)

1 Finding the Extrema among a Point Set in a Delaunay Cell

Recall that a Delaunay cell is an interval in 1D space, a triangle in 2D space, and a tetrahedron in 3D space. Extreme points or extrema are defined in a local or restricted sense, e.g., points closest to the center in a vertex or edge region or closest to the opposite edge in a vertex region, etc of a Delaunay cell. Such points are usually the best candidates for the (minimum) dominating sets for PCDs.

2 The Extreme Points in a General Triangle

First we define the same triangle $$T$$ used in the previous sections

A<-c(1,1); B<-c(2,0); C<-c(1.5,2);
Tr<-rbind(A,B,C);

n<-10  #try also n<-20 or 100

And we generate $$n=$$ 10 uniform points in it using the function runif.tri.

set.seed(1)
Xp<-runif.tri(n,Tr)$g 2.1 Closest Points in Vertex Regions to the Opposite Edges Here an extrema point in each $$M$$-vertex region in a triangle $$T$$, where $$M$$ is a center, is the point in the given data set, $$\mathcal{X}_n$$ closest to the opposite edge. That is, for the triangle $$T(A,B,C)$$, if the $$M$$-vertex region for vertex $$A$$ is $$V(A)$$, then the opposite edge is edge $$BC$$, and closest point in $$\mathcal X_n \cap V(A)$$ to edge $$BC$$ is found (if there are no data points in $$V(A)$$, the function returns NA for the vertex region $$V(A)$$). These extrema are used to find the minimum dominating set and hence the domination number of the PE-PCD, since a subset (possibly all) of this type of extrema points constitutes a minimum dominating set (see Ceyhan and Priebe (2007), Ceyhan and Priebe (2005), and Ceyhan (2011) for more details). With M=CC (i.e., when the center is the circumcenter), the extrema point here is the closest $$\mathcal{X}$$ point in CC-vertex region to the opposite edge, and is found by the function cl2edgesCCvert.reg which is an object of class Extrema and has arguments Xp,tri where • Xp, a set of 2D points representing the set of data points and • tri, a $$3 \times 2$$ matrix with each row representing a vertex of the triangle. Its call (with Ext in the below script) just returns the type of the extrema. Its summary returns the type of the extrema, the extrema points, distances between the edges and the closest points to the edges in CC-vertex regions, vertices of the support of the data points. The plot function (or plot.Extrema) would return the plot of the triangle together with the CC-vertex regions and the generated points with extrema being marked with red crosses. Ext<-cl2edgesCCvert.reg(Xp,Tr) Ext #> Call: #> cl2edgesCCvert.reg(Xp = Xp, tri = Tr) #> #> Type: #> [1] "Closest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) \n to the Opoosite Edges" summary(Ext) #> Call: #> cl2edgesCCvert.reg(Xp = Xp, tri = Tr) #> #> Type of the Extrema #> [1] "Closest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) \n to the Opoosite Edges" #> #> Extremum Points: Closest Points in CC-Vertex Regions of the Triangle to its Edges #> (Row i corresponds to vertex region i for i=1,2,3) #> [,1] [,2] #> [1,] 1.723711 0.8225489 #> [2,] 1.794240 0.2158873 #> [3,] 1.380035 1.5548904 #> [1] "Vertex labels are A=1, B=2, and C=3 (correspond to row number in Extremum Points)" #> #> Distances between the Edges and the Closest Points to the Edges in CC-Vertex Regions #> (i-th entry corresponds to vertex region i for i=1,2,3) #> [1] 0.06854235 1.06105561 0.66109225 #> #> Vertices of the Support Triangle #> [,1] [,2] #> A 1.0 1 #> B 2.0 0 #> C 1.5 2 plot(Ext) With M=CM (i.e., when the center is the center of mass), the extrema point here is the closest $$\mathcal{X}$$ point in CM-vertex region to the opposite edge, and is found by the function cl2edgesCMvert.reg which is an object of class Extrema. Its arguments, call, summary and plot are as in cl2edgesCCvert.reg. Ext<-cl2edgesCMvert.reg(Xp,Tr) Ext #> Call: #> cl2edgesCMvert.reg(Xp = Xp, tri = Tr) #> #> Type: #> [1] "Closest Points in CM-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) \n to the Opposite Edges" summary(Ext) #> Call: #> cl2edgesCMvert.reg(Xp = Xp, tri = Tr) #> #> Type of the Extrema #> [1] "Closest Points in CM-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) \n to the Opposite Edges" #> #> Extremum Points: Closest Points in CM-Vertex Regions of the Triangle to its Edges #> (Row i corresponds to vertex region i for i=1,2,3) #> [,1] [,2] #> [1,] 1.316272 1.0372685 #> [2,] 1.687023 0.7682074 #> [3,] 1.482080 1.1991317 #> [1] "Vertex labels are A=1, B=2, and C=3 (correspond to row number in Extremum Points)" #> #> Distances between the Edges and the Closest Points to the Edges in CM-Vertex Regions #> (i-th entry corresponds to vertex region i for i=1,2,3) #> [1] 0.4117393 0.7181527 0.4816895 #> #> Vertices of the Support Triangle #> [,1] [,2] #> A 1.0 1 #> B 2.0 0 #> C 1.5 2 plot(Ext) With a general center M in the interior of the triangle $$T$$, the extrema point here is the closest $$\mathcal{X}$$ point in $$M$$-vertex region to the opposite edge, and is found by the function cl2edgesMvert.reg which is an object of class Extrema and has arguments Xp,tri,M,alt where • Xp,tri are as in cl2edgesCCvert.reg. • M, a 2D point in Cartesian coordinates or a 3D point in barycentric coordinates which serves as a center in the interior of the triangle tri or the circumcenter of tri; which may be entered as “CC” as well; • alt, a logical argument for alternative method of finding the closest points to the edges, default alt=FALSE. When alt=FALSE, the function sequentially finds the vertex region of the data point and then the minimum distance to the opposite edge and the relevant extrema objects, and when alt=TRUE, it first partitions the data set according which vertex regions they reside, and then finds the minimum distance to the opposite edge and the relevant extrema on each partition. Its call, summary and plot are as in cl2edgesCCvert.reg. We comment the plot(Ext) out below for brevity in the exposition, as the plot is similar to the one in cl2edgesCMvert.reg above. M<-c(1.6,1.0) #try also M<-as.numeric(runif.tri(1,Tr)$g)
Ext<-cl2edgesMvert.reg(Xp,Tr,M)
Ext
#> Call:
#> cl2edgesMvert.reg(Xp = Xp, tri = Tr, M = M)
#>
#> Type:
#> [1] "Closest Points in M-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2)\n to Opposite Edges"
summary(Ext)
#> Call:
#> cl2edgesMvert.reg(Xp = Xp, tri = Tr, M = M)
#>
#> Type of the Extrema
#> [1] "Closest Points in M-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2)\n to Opposite Edges"
#>
#>  Extremum Points: Closest Points in M-Vertex Regions of the Triangle to its Edges
#>  (Row i corresponds to vertex region i for i=1,2,3)
#>          [,1]      [,2]
#> [1,] 1.482080 1.1991317
#> [2,] 1.687023 0.7682074
#> [3,] 1.380035 1.5548904
#> [1] "Vertex labels are A=1, B=2, and C=3 (correspond to row number in Extremum Points)"
#>
#>  Distances between the Edges and the Closest Points to the Edges in M-Vertex Regions
#>  (i-th entry corresponds to vertex region i for i=1,2,3)
#> [1] 0.2116239 0.7181527 0.6610922
#>
#>  Vertices of the Support Triangle
#>   [,1] [,2]
#> A  1.0    1
#> B  2.0    0
#> C  1.5    2
plot(Ext)

There is also the function cl2edges.vert.reg.basic.tri which takes arguments Xp,c1,c2,M and finds the closest points in a data set Xp in the $$M$$-vertex regions to the corresponding (opposite) edges in the standard basic triangle, $$T_b$$ where the standard basic triangle is $$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$$.

2.2 Closest Points to the Circumcenter in CC-Vertex Regions

Here an extrema point in each CC-vertex region is the point in the given data set, $$\mathcal{X}_n$$ closest to the circumcenter (CC). That is, for the triangle $$T(A,B,C)$$, if the $$CC$$-vertex region is $$V(A)$$, the closest point in $$\mathcal X_n \cap V(A)$$ to the circumcenter is found (if there are no data points in $$V(A)$$, the function returns NA for the vertex region $$V(A)$$).

The description and summary of extrema points and their plot can be obtained using the function cl2CCvert.reg which is an object of class Extrema and takes arguments Xp,tri,ch.all.intri where

• Xp,tri are as in cl2edgesCCvert.reg and
• ch.all.intri is a logical argument (default=FALSE) to check whether all data points are inside the triangle tri. So, if it is TRUE, the function checks if all data points are inside the closure of the triangle (i.e., interior and boundary combined) else it does not.

Its call, summary and plot are as in cl2edgesCCvert.reg, except in summary distances between the circumcenter and the closest points to the circumcenter in CC-vertex regions are provided.

Ext<-cl2CCvert.reg(Xp,Tr)
Ext
#> Call:
#> cl2CCvert.reg(Xp = Xp, tri = Tr)
#>
#> Type:
#> [1] "Closest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) to its Circumcenter"
summary(Ext)
#> Call:
#> cl2CCvert.reg(Xp = Xp, tri = Tr)
#>
#> Type of the Extrema
#> [1] "Closest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) to its Circumcenter"
#>
#>  Extremum Points: Closest Points in CC-Vertex Regions of the Triangle to its Circumcenter
#>  (Row i corresponds to vertex i for i=1,2,3)
#>          [,1]      [,2]
#> [1,] 1.723711 0.8225489
#> [2,] 1.794240 0.2158873
#> [3,] 1.529720 1.5787125
#> [1] "Vertex labels are A=1, B=2, and C=3 (correspond to row number in Extremum Points)"
#>
#>  Distances between the Circumcenter and the Closest Points to the Circumcenter in CC-Vertex Regions
#>  (i-th entry corresponds to vertex i for i=1,2,3)
#> [1] 0.4442261 0.9143510 0.7428921
#>
#>  Vertices of the Support Triangle
#>   [,1] [,2]
#> A  1.0    1
#> B  2.0    0
#> C  1.5    2
plot(Ext)  

There is also the function cl2CCvert.reg.basic.tri which takes arguments Xp,c1,c2,ch.all.intri and finds the closest points in a data set Xp in the CC-vertex regions to the circumcenter in the standard basic triangle, $$T_b$$.

2.3 Furthest Points from Vertices in CC-Vertex Regions

Here an extrema point in each CC-vertex region is the point in the given data set, $$\mathcal{X}_n$$ furthest to the corresponding vertex. That is, for the triangle $$T(A,B,C)$$, if the $$CC$$-vertex region is $$V(A)$$, the furthest point in $$\mathcal X_n \cap V(A)$$ from the vertex $$A$$ is found (if there are no data points in $$V(A)$$, the function returns NA for the vertex region $$V(A)$$).

The description and summary of extrema points and their plot can be obtained using the function fr2vertsCCvert.reg which is an object of class Extrema. Its arguments, call, summary and plot are as in cl2edgesCCvert.reg, except in summary distances between the vertices and the furthest points in the CC-vertex regions are provided. We comment the plot(Ext) out below for brevity in the exposition, as the plot is a special case of the one in kfr2vertsCCvert.reg with $$k=1$$ below.

Ext<-fr2vertsCCvert.reg(Xp,Tr)
Ext
#> Call:
#> fr2vertsCCvert.reg(Xp = Xp, tri = Tr)
#>
#> Type:
#> [1] "Furthest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) from its Vertices"
summary(Ext)
#> Call:
#> fr2vertsCCvert.reg(Xp = Xp, tri = Tr)
#>
#> Type of the Extrema
#> [1] "Furthest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) from its Vertices"
#>
#>  Extremum Points: Furthest Points in CC-Vertex Regions of the Triangle from its Vertices
#>  (Row i corresponds to vertex i for i=1,2,3)
#>          [,1]      [,2]
#> [1,] 1.723711 0.8225489
#> [2,] 1.794240 0.2158873
#> [3,] 1.380035 1.5548904
#> [1] "Vertex labels are A=1, B=2, and C=3 (correspond to row number in Extremum Points)"
#>
#>  Distances between the vertices and the furthest points in the vertex regions
#>  (i-th entry corresponds to vertex i for i=1,2,3)
#> [1] 0.7451486 0.2982357 0.4609925
#>
#>  Vertices of the Support Triangle
#>   [,1] [,2]
#> A  1.0    1
#> B  2.0    0
#> C  1.5    2
plot(Ext) 

There is also the function fr2vertsCCvert.reg.basic.tri which takes the same arguments as cl2CCvert.reg.basic.tri and returns the furthest points in a data set in the vertex regions from the vertices in the standard basic triangle, $$T_b$$.

2.4$$k$$ Furthest Points from Vertices in CC-Vertex Regions

Here extrema points in each CC-vertex region are the $$k$$ most furthest points in the given data set, $$\mathcal{X}_n$$ to the corresponding vertex. That is, for the triangle $$T(A,B,C)$$, if the $$CC$$-vertex region is $$V(A)$$, the $$k$$ most furthest points in $$\mathcal X_n \cap V(A)$$ from the vertex $$A$$ are found (if there are $$k'$$ with $$k'< k$$ data points in $$V(A)$$, the function returns $$k-k'$$ NA’s for at the end of the extrema vector for the vertex region $$V(A)$$).

The description and summary of extrema points and their plot can be obtained using the function kfr2vertsCCvert.reg. which is an object of class Extrema and takes arguments Xp,tri,k,ch.all.intri where Xp,tri,ch.all.intri are as in fr2vertsCCvert.reg and k represents the number of furthest points from each vertex. Its call, summary and plot are also as in fr2vertsCCvert.reg, except in summary distances between the vertices and the $$k$$ most furthest points to the vertices in the CC-vertex regions are provided.

k=3
Ext<-kfr2vertsCCvert.reg(Xp,Tr,k)
Ext
#> Call:
#> kfr2vertsCCvert.reg(Xp = Xp, tri = Tr, k = k)
#>
#> Type:
#> [1] "3 Furthest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) from its Vertices"
summary(Ext)
#> Call:
#> kfr2vertsCCvert.reg(Xp = Xp, tri = Tr, k = k)
#>
#> Type of the Extrema
#> [1] "3 Furthest Points in CC-Vertex Regions of the Triangle with Vertices A=(1,1), B=(2,0), and C=(1.5,2) from its Vertices"
#>
#>  Extremum Points: 3 Furthest Points in CC-Vertex Regions of the Triangle from its Vertices
#>  (Row i corresponds to vertex i for i=1,2,3)
#>                               [,1]      [,2]
#> 1. furthest from vertex 1 1.723711 0.8225489
#> 2. furthest from vertex 1 1.687023 0.7682074
#> 3. furthest from vertex 1 1.482080 1.1991317
#> 1. furthest from vertex 2 1.794240 0.2158873
#> 2. furthest from vertex 2       NA        NA
#> 3. furthest from vertex 2       NA        NA
#> 1. furthest from vertex 3 1.380035 1.5548904
#> 2. furthest from vertex 3 1.529720 1.5787125
#> 3. furthest from vertex 3 1.477620 1.7224190
#> [1] "Vertex labels are A=1, B=2, and C=3 (where vertex i corresponds to row numbers 3(i-1) to 3i in Extremum Points)"
#>
#>  Distances between the vertices and the 3 furthest points in the vertex regions
#>  (i-th entry corresponds to vertex i for i=1,2,3)
#>           [,1]      [,2]      [,3]
#> [1,] 0.3686516 0.7250712 0.3511223
#> [2,] 0.2982357        NA        NA
#> [3,] 0.4609925 0.4223345 0.2784818
#>
#>  Vertices of the Support Triangle
#>   [,1] [,2]
#> A  1.0    1
#> B  2.0    0
#> C  1.5    2
plot(Ext)

There is also the function kfr2vertsCCvert.reg.basic.tri which takes arguments Xp,c1,c2,k,ch.all.intri and finds the $$k$$ most furthest points in a data set Xp in the vertex regions from the corresponding vertices in the standard basic triangle, $$T_b$$.

2.5 Closest Points in the Standard Equilateral Triangle to its Edges

Here extrema points are the points in the given data set, $$\mathcal{X}_n$$ closest to the edges of the the standard equilateral triangle $$T_e=T(A,B,C)$$ with vertices $$A=(0,0)$$, $$B=(1,0)$$, and $$C=(1/2,\sqrt{3}/2)$$. That is, for the triangle $$T_e$$ the closest points in $$\mathcal X_n \cap T_e$$ to the edges of $$T_e$$ are found.

First we generate $$n=20$$ uniform points in the standard equilateral triangle $$T_e$$.

n<-10  #try also n<-20

4.1 Closest Points in Vertex Regions to the Opposite Faces

Here an extrema point in each $$M$$-vertex region, where $$M$$ is a center of the tetrahedron, is the point in the given data set, $$\mathcal{X}_n$$ closest to the opposite face. That is, for the tetrahedron $$T(A,B,C,D)$$, if the $$M$$-vertex region is $$V(A)$$, the opposite face is the triangular face $$T(B,C,D)$$, and closest point in $$\mathcal X_n \cap V(A)$$ to face $$T(B,C,D)$$ is found (if there are no data points in $$V(A)$$, the function returns NA for the vertex region $$V(A)$$).

With M=CC (i.e., when the center is the circumcenter), the extrema point here is the closest $$\mathcal{X}$$ point in CC-vertex region to the opposite face, and is found by the function cl2faces.vert.reg.tetra which is an object of class Extrema and takes arguments Xp,th,M where

• Xp1, a set of 3D points representing the set of data points.
• th1, a $$4 \times 3$$ matrix with each row representing a vertex of the tetrahedron.
• M1, the center to be used in the construction of the vertex regions in the tetrahedron,th. Currently it only takes“CC”for circumcenter and“CM”for center of mass; default=“CM”.

This function is the 3D version of the function cl2edgesCCvert.reg Its call, summary and plot are as in cl2edgesCCvert.reg, except in summary distances between the faces and the closest points to the faces in CC-vertex regions are provided.

Ext<-cl2faces.vert.reg.tetra(Xp,tetra,Cent)
Ext
#> Call:
#> cl2faces.vert.reg.tetra(Xp = Xp, th = tetra, M = Cent)
#>
#> Type:
#> [1] "Closest Points in CC-Vertex Regions of the Tetrahedron with Vertices A=(-0.12,-0.15,0.06), B=(0.94,0.2,-0.22), C=(0.54,1.09,-0.15), and D=(0.7,0.37,0.65) to the Opposite Faces"
summary(Ext)
#> Call:
#> cl2faces.vert.reg.tetra(Xp = Xp, th = tetra, M = Cent)
#>
#> Type of the Extrema
#> [1] "Closest Points in CC-Vertex Regions of the Tetrahedron with Vertices A=(-0.12,-0.15,0.06), B=(0.94,0.2,-0.22), C=(0.54,1.09,-0.15), and D=(0.7,0.37,0.65) to the Opposite Faces"
#>
#>  Extremum Points: Closest Points in CC-Vertex Regions of the Tetrahedron to its Faces
#>  (Row i corresponds to face i for i=1,2,3,4)
#>           [,1]      [,2]       [,3]
#> [1,] 0.1073281 0.0109421 0.19871179
#> [2,] 0.6535570 0.2922984 0.15795015
#> [3,] 0.5199352 0.6610763 0.08954581
#> [4,] 0.5127296 0.5449680 0.24057920
#> [1] "Vertex labels are A=1, B=2, C=3, and D=4 (correspond to row number in Extremum Points)"
#>
#>  Distances between Faces and the Closest Points to the Faces in CC-Vertex Regions
#>  (i-th entry corresponds to vertex region i for i=1,2,3,4)
#> [1] 0.7554212 0.2773495 0.4803672 0.3509001
#>
#>  Vertices of the Support Tetrahedron
#>         [,1]       [,2]        [,3]
#> A -0.1172457 -0.1491590  0.06455702
#> B  0.9360619  0.1991948 -0.21910686
#> C  0.5364267  1.0883630 -0.14701271
#> D  0.7041039  0.3690740  0.65477496
plot(Ext)`

References

Ceyhan, E. 2008. “The Distribution of the Domination Number of Class Cover Catch Digraphs for Non-Uniform One-Dimensional Data.” Discrete Mathematics 308(23): 5376–93.
———. 2011. “Spatial Clustering Tests Based on Domination Number of a New Random Digraph Family.” Communications in Statistics - Theory and Methods 40(8): 1363–95.
———. 2020. “Domination Number of an Interval Catch Digraph Family and Its Use for Testing Uniformity.” Statistics 54(2): 310–39.
Ceyhan, E., and C. E. Priebe. 2005. “The Use of Domination Number of a Random Proximity Catch Digraph for Testing Spatial Patterns of Segregation and Association.” Statistics & Probability Letters 73(1): 37–50.
———. 2007. “On the Distribution of the Domination Number of a New Family of Parametrized Random Digraphs.” Model Assisted Statistics and Applications 1(4): 231–55.
Priebe, C. E., J. G. DeVinney, and D. J. Marchette. 2001. “On the Distribution of the Domination Number of Random Class Cover Catch Digraphs.” Statistics & Probability Letters 55(3): 239–46.