Graphics Reference
In-Depth Information
Figure 5.5.
Representation scheme.
Figure 5.6.
Example of ambiguous repre-
sentation scheme.
Definition.
A
representation scheme
, or simply
representation
, of a set of “objects”
O
using a set
L
is a relation r between
O
and
L
. If (x,y) Πr, then we shall say that y
rep-
resents
x. A representation scheme r is
unambiguous
(or
complete
) if r is one-to-one.
A representation scheme r is
unique
if r is a function (that is, single-valued). The ele-
ments of
L
are called
representations
or
syntactically correct representations
and those
in the range of r are called the
semantically correct
or
valid representations
.
See Figure 5.5. The term “syntactically/semantically correct” is used, because if r
is a representation scheme, we can think of r(x) as a set of encodings for x in a “lan-
guage”
L
. The semantically correct elements of
L
are those “sentences” which have a
“meaning” in that there is an object that corresponds to them. The terms unambigu-
ous and unique separate out those relations that are
not
many-to-one or one-to-many,
respectively. To be unambiguous means that if one has the encoding, then one knows
the object to which it corresponds. To be unique means that there is only one way to
encode an object.
5.3.1 Example.
Let
O
be the set of polygons in the plane that have positive area
but no holes. Let
L
be the set of finite sequences of points. For example, the sequence
(2,1), (-1,3), (4,5) belongs to
L
. Define a representation scheme for
O
using
L
by asso-
ciating to each object in
O
the set of its vertices listed in some order. This represen-
tation scheme is neither unambiguous nor unique. It is ambiguous because the objects
in Figures 5.6(a) and (b) both have the same vertices. It is not unique because the ver-
tices of an object can be listed in many ways. Furthermore, not all sequences of points
