Graphics Reference
In-Depth Information
Figure
.
.
Airline dataset
smallest open disk touching two points D
; the radius of this disk is half the distance
between the two points and the center of this diskis halfway between the two points.
We call an open disk of fixed radius D
(
r
)
.Wecallanopendiskoffixedradiusand
centered on a point D
(
p, r
)
.
Disk Exclusion
5.4.1
Several proximity graphs are defined by empty disks. hat is, edges exist in these
graphs when disks touching pairs of points are found to be empty.
Delaunay Triangulation
Ina Delaunaygraph, anedgeexistsbetween anypair ofpointsthat can betouched
by an open disk D containing no points.
heDelaunay triangulation anditsdual,theVoronoitessellation, arepowerfulstruc-
tures for characterizing distributions of points. While they have higher-dimensional
generalizations, their most frequent applications are in two dimensions. here are
several proximity graphs that are subsets of the Delaunay triangulation:
Convex Hull
A polygon is a closed plane figure with nverticesand n
faces.heboundary of
a polygon can be represented by a geometric graph whose vertices are the polygon
verticesandwhoseedgesarethepolygonfaces.Ahullofasetofpoints X inEuclidean
space R
is a collection of one or more polygons that have a subset of the points in
X for their vertices and that collectively contain all the points in X. his definition
includes entities that range from a single polygon to a collection of polygons each
consisting of a single point. A polygon is convex if it contains all the straight-line
segments connecting any pair of its points.
−
