Graphics Reference
In-Depth Information
An algorithm for computing Y Æ X f rom X Æ Y :
Let x
i
, 1 £ i £ |X| , and y
j
, 1 £ j £ |Y|, denote the objects of type X and Y, respectively.
for
j:=1
to
|Y|
do
begin
Initialize a set X
j
of objects of type X to empty;
for
i:=1
to
|X|
do
begin
One direct access gives us x
i
Æ Y;
If y
j
Π(x
i
Æ Y) then X
j
= X
j
» { x
i
};
end
end
;
The collection of sets X
j
now constitutes Y Æ X .
Algorithm 5.8.1.1.
Computing the inverse adjacency relation Y
Æ
X.
arguments here but simply refer the interested reader to that paper. Rather, we want
to concentrate on the answer to (2) and summarize the main results of [NiBl94]. It
should be noted however, that all the adjacency relations that we mention later on as
having the best complexity properties are also topologically adequate.
First of all, as Ni and Bloor point out, we need to distinguish between complex-
ity in the context of a particular implementation and complexity at the abstract data
structure level. [NiBl94] analyze the latter, which is implementation independent, and
give answers in terms of the number of direct accesses of information and the number
of set operations, such as union, intersection, etc., that are needed. A discussion of
the costs involved in the context of some specific implementations, in particular, edge-
based ones, can be found in [Weil85].
As an example of how one can compute the implementation independent cost of
an adjacency relation that may be needed for an algorithm, suppose that a single non-
self-relation X Æ Y is given. Algorithm 5.8.1.1 computes the inverse adjacency rela-
tion Y Æ X. The cost of this algorithm is |X| direct accesses, |X| set membership tests,
and at most |X||Y| unions for a total of 2|X| + |X||Y| steps. Ni and Bloor analyze in a
similar way the costs of all the other possible queries for any given set of adjacency
relations. One relation, namely, the E Æ E relation, is treated as a special case. Some-
times data structures are used that do not store all objects adjacent to a given object.
For historical reasons, due to the influential papers [Baum72] and [Baum75], the
edge-edge adjacency relation has come to denote a more restricted relation in that
only two of the edges adjacent to a given edge are listed.
Baumgart's Winged Edge Representation.
In this representation each face is
assumed to be bounded by a set of disjoint edge cycles. One of these is the outside
