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

for each edge and their boundaries. This partitioning, the boundary structure
in particular, is called the straight skeleton of the polygon P [ 2 ]. Figure 8 shows
an example of a polygon (thick lines) and the corresponding straight skeleton
(thin lines). The straight skeleton has applications in many fields, such as paper
folding [ 6 ], solid modeling [ 27 ], and pop-up cards [ 23 ].
Fig. 8. Polygon and its straight skeleton.
The straight skeleton can be defined for a more general structure, a straight-
line graph, and Huber and Held [ 12 ] constructed an O( n 2 log n ) algorithm for the
generalized straight skeleton. For the straight skeleton of a simple polygon, an
O( n 3 / 2 log n ) algorithm is known [ 4 ]. However, these algorithms are theoretical in
the sense that they are designed on the assumption that numerical computation
is done precisely. Therefore they are not necessarily valid in actual comput-
ers because of numerical errors. In this paper, we apply the topology-oriented
principle [ 22 , 25 ] which we have developed for designing robust geometric algo-
rithms, and construct a new algorithm which is robust against numerical errors
and which runs in O( n 2 log n ) time, and thus show that the topology-oriented
approach is similar to persistent human brain computation.
The straight skeleton can be interpreted as a roof structure in three-dimensional
space, in the following manner. Suppose that the polygon P is the shape of the
wall seen from above, all parts of the wall have the same height, and we want to
construct a roof structure in which all parts have the same angle of declination.
The straight skeleton of P tells us how to partition the roof into planar plates
so that this is possible. Indeed, to build this roof, the region assigned to an edge
of P should be elevated to a roof plate passing through the edge at the top of
the wall.
On the basis of this interpretation, we can construct a sweep algorithm for
the straight skeleton. Let ˀ be a horizontal plane that is initially placed on top
of the wall. We let ˀ sweep upward and, in this way, construct the roof structure
inside P step by step from the lower part to the highest point on the roof. Next,