Computational Geometry in the Human Brain - Discrete and Computational Geometry and Graphs - page 153

Intuitively, this algorithm constructs the roof structure below the sweep plane
ˀ step by step as ˀ moves upward. However, an inconsistency may arise due to
numerical errors in the computations. Let P be the regular polygon shown in
Fig. 9 (a). In theory, all the roof edges emanating from the vertices meet at a
common point. However, in the real world, we have numerical errors, and hence
it is dicult to identify this common point of intersection. Instead, the algorithm
may find many points of intersection. Suppose that Algorithm 1 first finds the
point of intersection of a roof edge and a roof plate as shown in Fig. 9 (b), and
next finds another pair, as shown in Fig. 9 (c). However, this is contradictory
because the roof edges cross each other, which should not happen in the roof
structure. Therefore, Algorithm 1 is not robust against numerical errors.
We can modify this algorithm and make it robust by using what we observed
in the previous section about how the brain performs such computation. For this
purpose, we first classify the roof edges into three types.
Let us concentrate on the structure below the sweep plane ˀ . As shown in
Fig. 10 (a), the initial roof edges terminate at the points of intersection with
ˀ , and the intersection of the roof plates and ˀ form a cycle represented by
broken lines in this figure. We call the roof edges that terminate at the points of
intersection with ˀ ,the active edges , meaning that these edges are still growing.
We call the cycle formed by the intersection of the roof plates and ˀ a forefront
cycle , meaning that it is moving toward the inside of the polygon P . Furthermore,
we call the roof plates at the forefront cycles the active roof plates , meaning that
they are still growing.

( (

Fig. 10. Active edges, forefront cycles, and fixed edges.

Initially, all the roof edges and roof plates are active. After the sweep plane ˀ
has moved to some extent, some of roof edges below ˀ are completed, as shown
by the solid lines in Fig. 10 (b). We call these roof edges fixed edges . In other
words, edges in E are active, while edges in E are fixed. Similarly, some of the
roof plates become completely bounded by roof edges. We call those roof plates