Graphics Reference
In-Depth Information
Disk Inclusion
5.4.2
Several proximity graphs are defined by disk inclusion. hat is, edges exist in these
graphs when predefined disks contain pairs of points. hese graphs are not generally
subsets of the Delaunay triangulation.
In a k-nearest-neighbor graph (KNN), a directed edge exists between a point p
and a point q if d
(
p, q
)
is among the k smallest distances in the set
d
(
p, j
)
. Most applications restrict KNN to a simple graph by removing
self loops and edge weights. If k
j
n, j
p
,
this graph may not be planar. Figure
.
shows a nearest-neighbor graph for
=
, this graph is a subset of the MST. If k
Figure
.
.
Nearest-neighbor graph
Figure
.
.
-Nearest-neighbor graph
