Graphics Reference
In-Depth Information
can be listed in a circular order based on the angle that a shortest path to that vertex
makes with a fixed line at the start point. Using such an order, connect the flattened
vertices by edges in the order in which they are listed. This generates a circular loop
called the
equator
that cuts the flattened surface into two regions called the
arctic
region
(the one containing the start point) and the
antarctic region
. One can show that
the Voronoi diagram is a tree with O(n) edges. Therefore, it can be built in time
O(n log n) and space O(n). The subdivision of the surface induced by the subdivision
of the layout can be built in time O(n
2
).
This completes the sketch of how one finds shortest paths in convex surfaces. If
the surface is not convex, the steps in the algorithm have to be modified but fortu-
nately the complexity of the steps does not change in the end. The final result for sur-
faces, convex or not, is stated below.
15.3.2.6 Theorem.
Let
S
be an arbitrary polygonal surface with n edges and
let
p
be a fixed point on
S
. After a preprocessing time of O(n
2
) and using space
O(n
2
), the Chen and Han algorithm answers any query about the shortest distance
from a point
q
on
S
to
p
in time O(log n) and the shortest path from
p
to
q
can
be generated in time O(k + log n), where k is the number of edges intersected by the
path.
Proof.
See [CheH90].
The Chen and Han algorithm improved on the one in [MiMP87], which was an
O(n
2
log n) algorithm, but it and the better O(n log
2
n) Kapoor algorithm are too com-
plicated and slow to be practical if one wants accurate answers since one would have
to represent computations with a number of bits that is an exponential function of
the number of bits in the coordinates of a vertex. For that reason, algorithms have
been developed that only give an approximate answer but which are much more
efficient. See, for example, the paper by Agarwal et al. ([AgHK00]).
15.4
Filament Winding and Tape Laying
The previous two sections described the mathematics involved in generating geo-
desics on surfaces. One area of manufacturing where geodesics play a role is in
winding filaments or tapes around mandrels to create composite materials. Filament
winding is a reinforcement method for creating composites that have high strength
and low weight. These materials are created by encasing filaments or fibrous tapes
in a resin matrix. The matrix holds the fibers in place, transfers stresses between
them, and also seals them from mechanical or environmental damage. The filament
or tape and matrix combination is wound around a mandrel that corresponds to the
desired shape of the finished material. Surfaces of revolution, or cylindrical surfaces
as a special case, are common shapes for these mandrels. At the end, after the mate-
rial is cured, the mandrel may become part of the finished product or be discarded.
The method is widely used in aerospace, hydrospace, military, and many other
applications. It is the mathematical aspect of the subject that interests us here, in
particular, the role that geodesics play. For manufacturing and other details the
