Graphics Reference
In-Depth Information
(1) The map r is continuous.
(2) If p is simple, then r|(0,1) is a homeomorphism between (0,1) and |p|-{
p
0
,
p
k
}.
If p is simple and not closed, then r is a homeomorphism between [0,1] and |p|.
Proof.
Easy.
Definition.
Let p be a pwl curve and r its standard parameterization. Let
p
and
q
be two points in the path of p. Choose s and t, so that s £ t,
p
=r(s), and
q
=r(t). The
set r([s,t]) is called
the part of the path of p from
p
to
q
.
The part of a path of a pwl curve is not well-defined in general because there may
be many choices for the parameters s and t (the curve may backtrack on itself, for
example). However, for simple curves it is well-defined unless the curve is closed and
one of the points is the first or last point of the curve.
After these preliminary definitions, we come to the first basic fact about shortest
curves, namely, that they exist.
15.3.2.2
Theorem.
Let
S
be a connected compact polygonal surface.
(1) Any two points of
S
can be connected by a shortest pwl curve, meaning that
any other pwl curve between the points will have a length that is larger than or equal
to the length of that curve. In fact, a shortest pwl curve between two points will have
length less than or equal to the length of any rectifiable curve between those two
points, not just pwl curves.
(2) Every shortest pwl curve between two points of
S
is a simple curve but there
may be more than one shortest curve between two points.
(3) There is a d>0, so that, for any two points
p
and
q
in
S
with |
pq
|<d, there
is a unique shortest pwl curve from
p
to
q
.
Proof.
By cutting along edges one can flatten the whole surface out in the plane, so
that one can study curves on the surface by studying curves in planar polygons. It is
a well-known fact that the shortest parametric curve between two points in the plane
traces out the segment between the points.
Just like in the smooth case, shortest pwl curves are a special case of a more
general type of pwl curve.
Definition.
A pwl curve p in a polygonal surface
S
is called a
discrete geodesic
if it
is locally the shortest pwl curve. More precisely, there is a d>0, so that, for any s,
t Œ [0,1], s £ t, with |s - t|<d, the pwl curve induced by [s,t] with respect to the stan-
dard parameterization r of p is a shortest pwl curve between r(s) and r(t).
Intuitively, a discrete geodesic has the property that if two points
p
and
q
in its
path are sufficiently close, then the part of the path from
p
to
q
is the path of a short-
est pwl curve from
p
to
q
. Just like in the smooth case, geodesics are not necessarily
the shortest curves between points. For example, on a cube a geodesic between two
points may pass those points more than once as it wraps around the cube multiple
times. On the other hand, it is obvious that every shortest pwl curve is a discrete
geodesic.
The discrete geodesic problem:
Given two points
p
and
q
on a polygonal surface
S
, find
a shortest pwl curve in
S
from
p
to
q
.
