VIETNAM NATIONAL UNIVERSITY, HANOI
VNU UNIVERSITY OF SCIENCE

DONG VAN VIET

FUNNEL TECHNIQUE FOR FINDING
SHORTEST PATHS FROM A FIXED SOURCE POINT
TO ALL DESTINATION POINTS ON A CONVEX
3
POLYHEDRAL SURFACE IN R

MASTER THESIS IN MATHEMATICS

HANOI - 2017


VIETNAM NATIONAL UNIVERSITY, HANOI
VNU UNIVERSITY OF SCIENCE

DONG VAN VIET

FUNNEL TECHNIQUE FOR FINDING
SHORTEST PATHS FROM A FIXED SOURCE POINT
TO ALL DESTINATION POINTS ON A CONVEX
3
POLYHEDRAL SURFACE IN R

Major: Applied Mathematics
Code:

60 46 01 12

MASTER THESIS IN MATHEMATICS

Supervisor: Assoc. Prof. Dr. Phan Thanh An

HANOI - 2017


Contents
Acknowledgements
List of symbols
Introduction
1 Preliminaries
1.1
1.2
1.3
1.4

The length of a path . . . . . . . . . . . . .
The space of paths . . . . . . . . . . . . . .
The length metric . . . . . . . . . . . . . . . .
Polyhedral convex sets . . . . . . . . . . .

2 Shortest paths on a polyhedral surface

2.1 Shortest paths on a polyhedral surface
2.1.1
2.1.2
2.1.3
2.2 Chen and Han’s algorithm . . . . . . . . .

2.2.1
2.2.2
2.2.3
2.3 An implementation of Chen and Han’s
3 Funnel technique for finding shortest paths
3.1
3.2
3.3
3.4
3.5
Conclusions
References

1

Definition of funnels . . . . . . . . . . . . . .
Funnel tree . . . . . . . . . . . . . . . . . . . .
The algorithm . . . . . . . . . . . . . . . . . . .
Examples . . . . . . . . . . . . . . . . . . . . . .
A military path planning algorithm . . .


Acknowledgements
First of all, I would like to express my most sincere gratitude and
appre-ciation to my supervisor Phan Thanh An. The work on this thesis
could not have been started if it were not for the generous support and
the detail guide provided by my instructor. I am indebted to his advice
during time of writing this thesis. He provided helpful feedback, support
and valuable advice in writing this thesis.
There are many people who have provided me with their insightful

comments and generously shared their document and knowledge. I
would like to thank, in particular, Assoc. Prof. Dr. Tran Van Hoai, Mrs.
Phong Thi Thu Huyen, Mrs. Nguyen Thi Le, for their advice.
I want to show my gratitude to all teachers from Faculty of
Mathemat-ics, Mechanics, and Informatics, who had taught me a lot of
knowledge through years.
In the process of doing this thesis, I received much important
encour-aging factor and support from university, teachers, and friends.
I would like to thank those people who have contributed significantly to
this thesis. Last but not least, I would like to thank my family for their
support over the years.

2


List of symbols
[a; b]

A closed line segment
joining a and b

]a; b]

[a; b]nfag

E

A sequence of common edges

F


A sequence of adjacent triangles

F

p;q;F

fk
fk
(f1; : : : ; fm)

A sequence of
adjacent triangles

A path in a metric space
L( )
P roj
The surface of a polyhedron

S

(s;
(a; b)
F

s

e

(a; b)


s; P roj


3


Introduction
The single source shortest path problem which asks computing the exact shortest paths from a fixed source point to all the other points on a
polyhedral surface is a well-studied problem in computational geometry. It
has many application areas such as path planning for the movement of
vehicles, robots, geographic information systems and navigation.
3

Sharir and Schorr [13] first presented an O(n logn) algorithm that runs on
the surface of a convex polytope, where n is the vertices of the polytope.
2

The algorithm was subsequently improved by Mount [9] to O(n log n) time
using what the author called the continuous Dijskstra technique.
2

Chen and Han [4] provided an O(n ) algorithm for single source shortest
path problem on nonconvex polytope which deviates from the conventional
continuous Dijskstra technique. Chen and Han’s algorithm is conceptu-ally
simple. It builds a tree, called sequence tree, using planar unfolding
technique and projection method. The simplicity comes from a new observation of one angle one split" which results in upper bounding the
number of branches in the sequence tree. The algorithm is particularly
interesting and receives much attention and improvement. The algorithm
was implemented and published by Kaneva and O’Rourke [5].

In [2], An introduced the concept of funnels along sequence of triangles
in three-dimensional space and straightest geodesics inside a sequence of
triangles. The concept of straightest geodesics along sequence of triangles
are modified from the concept of straightest geodesics on a polyhedral
surface of Polthier and Schmies [11]. These concepts are used to compute
the exact shortest path between two points along sequence of triangles, by
constructing a sequence of funnels.
In this thesis, the concepts of funnels and funnel trees on the surface of
4


a polytope given by An in [3] are used to compute all shortest paths from
the fixed source point to any destination points on a polyhedral surface.
The structure of funnel tree including all shortest paths is modified from
Chen and Han’s algorithm [4]. However, the main difference between
Chen and Han’s algorithm and An’s method is that we do not use the
planar unfolding technique and the concept of source images and the
projections of ones. An’s algorithm (Algorithm 5) builds the funnel tree of
funnels without planar unfolding technique. Consequently, the number of
opera-tions in An’s algorithm is relatively small comparing with the
number of operations in Chen and Han’s algorithm. The algorithm takes
2

O(m ) time, where m is the number of faces of the polytope.

The contents of this thesis are organized as follows. Chapter 1 reviews
the main definitions of paths, length of paths and polyhedral convex sets.
There always exists a path of minimal length between arbitrary two points in
a metric space. In Chapter 2, our aim is to prove some interesting properties of shortest paths on a convex polyhedral surface. Then we present
Chen and Han’s algorithm and an implementation of Kaneva and O’Rourke

for Chen and Han’s algorithm. We propose a new shortest path algorithm
using funnel technique in Chapter 3. Comparing to Chen and Han’s shortest path algorithm, An’s algorithm skips the unfolding steps. Instead of
building a sequence tree, a funnel tree is built. Therefore the proposed
algorithm theoretically outperforms in the step of planar unfolding.

The results in this thesis were presented at the seminar of the
Depart-ment of Numerical Analysis and Scientific Computing, Institute
of Math-ematics, VAST, Hanoi on November 8, 2017, and were
submitted to the 7th International Conference on High Performance
Scientific Computing, 2018 Hanoi, Vietnam
Hanoi, November 1st, 2017

Dong Van Viet

5


Chapter 1
Preliminaries
In this chapter, we review the definition of paths, length of paths in a
metric space based on [10] and the definition of polyhedral convex
sets based on [14]. The most important result here to remember says
that there always exists a path of minimal length between arbitrary two
points in a metric space.

1.1

The length of a path

Let X be a metric space. We denote by d(x; y) the distance between

two points x and y of X. We also use the notation d(x; y) = jx yj.
Definition 1.1.1 ([10]). A path in X is a continuous map : [a; b] ! X, where
a and b are two arbitrary real numbers satisfying a < b. If (a) = x and (b)
= y, then we say that x and y are the endpoints of , and that joins the
points x and y.
A partition, denoted by , of a closed interval [a; b] is defined to be a
finite sequence (ti)i=0;:::;n of real numbers satisfying a = t0 < t1 < < tn = b,
where n 1:
Definition 1.1.2 (The length of a path, [10]). The length of a path
[a; b] ! X is the quantity
n 1
X

LX ( ) = L( ) = sup

i=0

6

j (ti)

(ti+1)j;

:


where the supremum is taken over the set of partition = (ti)i=0;:::;n of [a;
b]. A path is said to be rectifiable if its length is finite.
3


Example 1.1.3. Let X = R equipped Euclidean norm. For all x and y in
3
3
3
R , let : [0; 1] ! R be a path joining x and y in R defined by
(t) = (1
t)x + ty. Then we have L( ) = kx
yk.
Proof. For all t1 and t2 satisfying 0
j (t1)

(t2)j = k(1

t2

t1)x + t1y

= k(t2

t1)kx

1, we have

(1

t1)x + (t1

= (t2

Thus, if


t1

t2)x

t2yk

t2)yk

yk:

= (ti)i=0;:::;n is an arbitrary partition of [0; 1], we have
n 1
X

j (ti) (ti+1)j =
i=0

Taking the supremum over all partition, we obtain
n 1
X

L( ) = sup

j (ti)

i=0

(ti+1)j = kx


yk:

Proposition 1.1.4 ([10]). Let : [a; b] ! X be a path, we obtain the
following inequality
jx yj L( );

where x = (a) and y = (b) are the endpoints of . Thus, the length of a
path is bounded below by the distance between its endpoints.
Proof. Let P be the set of all partition of [a; b]. For each partition = ft0; : :
: ; tng 2 P, set
n 1

X

L :=

i=0

j (ti)

(ti+1)j:

Let = fa; bg 2 P be a trivival partition of [a; b], then from the definition of
the length of a path we have
L( ) = sup L
2P

7



Let

be the set of all paths : [a; b] ! X that join x and y:

Definition 1.1.5. The shortest path joining x and y in X is a path, denoted by , that satisfies
L() = inf fL( )g:
2

In the next section, we shall see that for arbitrary two points x and y
in X, there always exists a shortest path joining them. But first we need
some definitions that will be used in the next section.
Definition 1.1.6 ([10]). Let : [a; b] ! X be a rectifiable path. We say that is
parametrized by arclength if for all u and v satisfying a u v b, we have v
u = L( j[u;v]).

Definition 1.1.7 ([10]). Let : [a; b] ! X be a path. We say that is
parametrized proportionally to arclength if either is a constant path, or
there exists a path

0

which satisfies =

0

: [c; d] ! X which is parametrized by arclength and

, where

: [a; b] ! [c; d] is the map defined by


(x) =

Proposition 1.1.8 ([10]). Let : [0; 1] ! X be a path parametrized proportionally to arclength. Then is an L( )-Lipschitz map.
Proof. If

: [0; 1] ! X is a constant path, then the conclusion follows
0

0

trivivally. Now suppose that
=
, where
: [c; d] ! X is a path
that is parametrized by arclength and where : [0; 1] ! [c; d] is defined by
(x) = (d c)x + c. Then, for all u and v satisfying 0 u v 1; we have
j (u)

0

0

(v)j = j ( (u))

( (v))j

0

L( j[ (u); (v)]) (using Proposition 1.1.4)

= (v)
= (d c)v

(u)
(d

(since

0

is parametrized by arclength)
c)u = (d
c)(v u)

0
= L( )(v u)
= L( )(v u):

8


1.2

The space of paths

Denote by C([a; b]; X) the set of paths in X with domain [a; b]. We
equip C([a; b]) with the metric defined by
j1

2j = sup j 1(t)

t2[a;b]

2(t)j;

for every 1 and 2 in C([a; b]; X). Then, C([a; b]; X) is topological space.
Proposition 1.2.1 ([10]). Let (fi)i2I be a family of maps from a topological
space E to R = R [ f ; 1g and let f : E ! R be the upper limit of this family,
that is, the map defined by f(x) = supi2I fi(x) for all x in E: Let x0 be a
point in E. If each fi is lower semi-continuous at x0, then f is also lower
semi-continuous at x0:
Proof. For every m < f(x0), there exists i0 in I such that m < fi0 (x0). Since
fi0 is lower semi-continuous at x0, we can find a neighborhood W of x0
such that for all x in W; we have m fi0 (x). Therefore, for all x in W , we
have m fi0 (x) f(x).
Theorem 1.2.2 (Lower semi-continuous of the length function, [10]).
The length function L : C([a; b]; X) ! R [ f1g is lower semi-continuous.
Proof. Let us set E = C([a; b]; X) and let us fix a point t 2 [a; b]. For any
0

0

and in E, we have j (t) (t)j j
defined by 7! (t) is continuous.
[a; b], the map V : E ! R defined by 7!V ( ) =

is a sum of continuous maps, and therefore it is
Proposition 1.2.1, the map 7!L( ) = sup V ( ) is lower semi-continuous.
Corollary 1.2.3 ([10]). Let ( n : [a; b] ! X)n 0 be a sequence of paths
converging uniformly to a path : [a; b] ! X. Then L( )
lim inf L( n):

n!1

Proof. From Theorem 1.2.2, the length function L is lower semicontinuous at every n in E: Then for every m satisfying m < L( ), there
exists a neighborhood W of in E such that for all

0

Since n as n ! 1, for every n large enough, n is in W , which implies
9

0

in W , we have m L( ):


m L( n). Hence by the definition of lower semi-continuous function, L( ) lim
infn!1 L( n).

Corollary 1.2.4 ([10]). For any real number M, the set of paths : [a; b] !
X

such that L( ) M is a closed subset of C([a; b]; X).

Proof. The uniform limit of a sequence of continuous maps is
continuous. Furthermore, if n : [a; b] ! X (n 0) is a sequence of paths
converging uniformly to a path and if L( n) M for all n, then we have, by
Corollary 1.2.3, L( ) M.
The following result is a particular case of a series of results which
are known under the name of Ascoli’s theorem .
Theorem 1.2.5 (Ascoli, [10]). Let Y be a separable metric space, let X

be a proper metric space and let (fn)n 0 be a uniformly equicontinuous
sequence of maps from Y to X such that for each y in Y , the sequence
(fn(y))n 0 is bounded. Then there exists a subsequence of (fn) that
convergers uniformly on every compact subset of Y to a map f : Y ! R,
and the limit map f is uniformly continuous.

Below is a few consequences of Theorem 1.2.5, applied to the
cases where the maps fn and paths:
Proposition 1.2.6 ([10]). Let X be a proper metric space, let M be a
nonnegative real number and for all n 0; let n : [0; 1] ! X be a path
parametrized proportionally to arclength and satisfying L( n) M. Suppose furthermore that the subset f n(0); n 0g of X is bounded. Then the
sequence of paths ( n)n 0 has a subsequence which convergers
uniformly to a path whose length is also M.
Proof. From Proposition 1.1.8 n is an L( n)-Lipschitz map for all n 0, the
sequence of maps ( n)n 0 is uniformly equicontinuous. Since the sequence ( n(0))n 0 is bounded and since the space X is proper, we can assume, up to replacing the sequence ( n)n 0 by a subsequence, that ( n(0))n
0 is convergent. Let x be the limit of this sequence. Then for all n 0 and
for all t in [0; 1], we have
jx

n(t)j = j n(0)

n(t)j
10

L( n)jt

0j

M:



Thus, for all t in [0; 1], the sequence ( n(t))n 0 is bounded. By Theorem 1.2.5,
there exists a subsequence of n which convergers uniformly to a path . By
Corollary 1.2.4, we have L( ) lim infn!1
L( n) M:

Proposition 1.2.7 (Existence of paths of minimal length, [10]). Let X be
a proper metric space, let x and y be two points in X and suppose that
there exists a rectifiable path in X joining x and y. Then there exists
such a path whose length is equal to the infimum of the lengths of
paths that join x and y:
Proof. Let = inffL( ) where is a path in X joining x and yg, and let be a sequence of paths joining x

( )
nn 0

and y satisfying L( n) ! .

Without loss of generality, we can assume that for every n 0, n is
parametrized proportionally to arclength and that its domain is the interval [0; 1]. By Proposition 1.2.6, there exists a subsequence of ( n)n 0 that
converges uniformly to a path . By taking limits, it is clear that the path

joins x and y. By Corollay 1.2.3, we have L( ) lim infn!1 L( n) = . From
the definition of , we also have L( ) ; which shows that L( ) =
.
The existence of a path of minimal length joining two given points in a
metric space is an interesting information and it leads to the existence of
shortest path joining two arbitrary points in a proper length space.

1.3


The length metric

Definition 1.3.1 ([10]). We say that a metric space X is connected by
rectifiable paths if for every x and y in X; there exists a rectifiable path
: [a; b] ! X such that (a) = x and (b) = y:

If (X; d) is metric space, define a map d‘ from X X to the extended
real line R [ f1g by setting
d‘(x; y) = inf L( );

where the infimum is taken over the set of paths

11

that join x and y.


Proposition 1.3.2 ([10]). Let (X; d) be a metric space that is connected
by rectifiable paths. Then d‘ is a metric on X and we have jx yjd d‘(x; y)
for every x and y in X:
Proof. Let x and y be two arbitrary points in X and let

: [a; b] ! X

be a path joining them. By Proposition 1.1.4, we have jx

djd

L( ),


which, by taking the infimum over all paths joining x and y, implies jx yjd
d‘(x; y).

Now let prove that d‘ is a metric. To every path : [a; b] ! X, we
0
0
associate a path : [a; b] ! X defined, for t 2 [a; b], by (t) = (a+b t). It is
0
0
clear that joins y and x and that L( ) = L( ). Thus, we have d‘(y; x) d‘(x;
y) for all x and y, which, by symmetry, implies d‘(x; y) = d‘(y; x).
Now suppose that d‘(x; y) = 0. From the inequality jx
yj
d‘(x; y) we
obtain jx yj = 0, which implies x = y: To prove that d‘ is a metric, it
remains to show that the triangle inequality is satisfied. Let x; y and z
0
be three arbitrary points in X, let k = d‘(x; y) and let k = d‘(y; z). For
any " > 0, let
: [a; b] ! X be a path joining x and y and satisfying
0

0

0

L( ) d‘(x; y) + "=2 and let : [a ; b ] ! X be a path joining y and z and
0
00

0 0
satisfying L( ) d‘(y; z) + "=2. We define the path [a; b + b a ] ! X be
setting

Obviously, we have L(

is obtained from

0

00

be the change of parameters : [b; b + b

defined by (t) = t + a
This implies
L(

j[a;b]) = L( ). On the other hand, the path

00

0

b. Therefore, we have L(

00

00


0

j[b;b+b0 a0]

j[b;b+b0

0

) = L( ) + L( ) d‘(x; y) + d‘(y; z) + ":
00

Taking the infimum over the paths
joining x and z, we obtain d‘(x; z)
d‘(x; y) + d‘(y; z) + ". Since this holds for every " > 0, we obtain d‘(x; z)
d‘(x; y) + d‘(y; z).
Definition 1.3.3 ([10]). We call the metric d‘, that is associated by
Propo-sition 1.3.2, to a metric space (X; d) that is connected by
rectifiable paths, the length metric of X associated to d.
12

00

=


Proposition 1.3.4 ([10]). Let (X; d) be a metric space and let : [a; b] ! (X;
d) be a rectifiable path. Then is continuous for metric d‘. In other word, the

map : [a; b] ! (X; d‘) is also a path.


Proof. For all t0 and t in [a; b], t0 < t, we have, by the additivity of length

d ( (t );
‘

0

(t))

L( j

[t0;t]

) = L( j

[a;t]

) L( j

[a;t0]

):

Because the map t 7!L( (t)) is continuous (see [10, Proposition 1.1.13]),
let t ! t0 we obtain d‘( (t0); (t)). This proves that is continuous with
respect to the metric d‘.
From the above two propositions, we see that (X; d‘) is a metric
space and : [a; b] ! (X; d‘) is also a path with the metric d‘ is defined by
d‘(x; y) = inf L( );


where the infimum is taken over the set of paths that join x and y. From
Proposition 1.2.7, for arbitrary two points x; y in X, there always exists
a path of minimal length joining them.

1.4

Polyhedral convex sets
n

Given two points a; b 2 R , the set of all points x = (1 )a + b such that
0 1 is called the (closed) line segment between a and b and denoted by
[a; b].
n

Definition 1.4.1 ([14]). A set C R is called convex if it contains any line
segment between two points of it, in other words, if (1 )a + b 2 C
whenever a; b 2 C; 0 1:
Example 1.4.2. Closed halfspaces which are sets of the form
fx j ha; xi

g; fx j ha; xi

or open halfspaces which are sets of the form
fx j ha; xi < g; fx j ha; xi > g

are examples of convex sets.
13

g;



Proposition 1.4.3 ([14]). The intersection of any collection of convex
sets is convex. If C; D are convex sets then C + D := fx + y j x 2 C; y 2
Dg, C = f x j x 2 Cg are covex sets.

Proof. If fC g is a collection of convex sets, and a; b 2 \ C , then for each

we have a 2 C ; b 2 C , therefore [a; b] C and hence, [a; b] \ C .
If C; D are convex sets, and a = x + y; b = u + v with x; u 2 C; y; v 2 D,
then (1 )a + b = [(1 )x + u] + [(1 )y + v] 2 C + D, for any
2 [0; 1], hence C + D is convex. The convexity of C can be proved
analogously.
Definition 1.4.4 ([14]). A convex set is said to be polyhedral if it is the
intersection of a finite family of closed halfspace. A polyhedral convex
set is also called a polyhedron.
In other words, a polyhedron is the solution set of a finite system of
linear inequalitites of the form
i

ha ; xi bi; i = 1; : : : ; m;

or in matrix form
Ax b;
i

m

where A is the m n matrix of rows a and b 2 R :
Definition 1.4.5 ([14]). A bounded polyhedron is called a convex polytope. A
finite union of convex polytopes such that its space is connected is called

a

polytope.
0

Definition 1.4.6 ([14]). A convex subset C of a convex set C is called a
0

face of C if any line segment in C with a relative point in C entirely lies
0

in C , i.e. if
x; y 2 C; (1 )x + y 2 F; 0 < < 1 ) [x; y] F:

Definition 1.4.7 ([14]). A 0-dimension face of a polyhedron D is called
an extreme point or a vertex, a 1-dimensional face of a polyhedron is
called an edge of the polydedron D.
14


n 3

In R

, the boundary of a polytope is called the surface of the polytope.

Then such a surface is formed by some faces of convex polytopes.
Theorem 1.4.8 ([12]). The following properties of a convex set D are
equivalent:
(a) D


is polyhedral;

(b) D

is closed and has only finitely many faces.

Proof. (a) implies (b). Let H1; : : : ; Hm be closed halfspaces whose inter0

0

section is D: Let D be a nonempty face of D. For each i; ri D must be
contained in int Hi or in the boundary hyperplane Mi of Hi (ri A is the relative interior of convex set A and int B is the interior of B). Let F be the
intersection of the finite collection consisting of the relatively open
0
convex sets int Hi or Mi containing ri D . This F is a convex subset of D;
0

and it is relatively open. Since ri D is a maximal relatively open convex
0

subset of D, we must have ri D = F: There are only finitely many
intersections of the form F , and different faces of D have disjoint
relative interiors, so it follows that C can have only finitely many faces.
implies (a). D is the intersection of its tangent closed halfspaces ([12,
Theorem 18.8]). If H is the boundary hyperplane of a tangent closed
(b)

halfspaces there exists by definition some x 2 D such that H is the unique
supporting hyperplane to D through x: Thus H is the unique supporting

hyperplane to C through the exposed face D \ H: Since D has only finitely
many faces, it follows that it can have only finitely many tangent closed
halfspaces. Hence C is polyhedral.

Remark 1.4.9. Base on the fundamental representation theorem for
con-vex sets, a polyhedron is completely determined by its vertices, its
edges and its faces.

15


Chapter 2
Shortest paths on a polyhedral
surface
In this chapter, firstly our aim is to present the statement of short-est
paths problem on a polyhedral surface. Secondly, we aim at proving
some interesting properties of shortest path on a convex polyhedral
sur-face. Thirdly, we present an algorithm of Chen and Han [4] for
determining the shortest paths between a source and a distination on a
polyhedral sur-face. Lastly, we present the implementation of Kaneva
and O’Rourke [5] for Chen and Han’s algorithm.

2.1

Shortest paths on a polyhedral surface

2.1.1

Problem statement


In this section, we concentrate on specifying the boundary or surface
of a polyhedron in three dimensional space. The surface of a polyhedron
is composed of three types of geometric objects: 0-dimensional vertices,
1-dimensional edges, and 2-dimensional faces. We consider faces to be
closed polygons and edges to be closed line segments.

Let S be the surface of a given polyhedron P , defined by a set F of
faces fi, a set E of edges ei, a set V of vertices vi. Let m be the number
of faces of P , so that P has also O(m) edges, vertices, and angles.
Then the number m is called the complexity of the polyhedron.
We are also given a special point s (the source point). In order to obtain
16


a unifrom model which is easy to work with, without loss of generality we
assume that all faces are triangles and that s is a vertex of the polyhedral
surface. We are asked to solve the following query form of the problem.

Problem 1 ([8]). Single source shortest path problem.
Require: A vertex s on a polyhedral surface S, which has been triangulated.
Ensure: Build a structure which allows one to compute a shortest path from
s to any query vertex t such that the path stays on the surface S:

Therefore, we are able to find the shortest path between the source
and any point on the surface.
2.1.2

Unfolding technique

Some terminologies introduced in [8] are used. Two triangles f and

0

f are said to be edge-adjacent (or adjacent for short) if the share a
common edge e:

Definition 2.1.1. A sequence of adjacent triangles is a list of one or
more triangles F = (f1; f2; : : : ; fm+1) such that triangle fi and triangle fi+1
share a common edge ei.

Figure 2.1: A sequence of adjacent triangles F = (f 1; f2; : : : ; fm+1).

In this thesis, we usually indentify F with f1 [f2 [: : : [fm+1, where the union
sign means to add one triangle to a sequence of adjacent triangles. The list
of edges E = (e1; e2; : : : ; em) with ei = fi \ fi+1, i = 1; : : : ; m will be called a
sequence of common edges, or the edge sequence. When an edge ei is a
closed segment with two end points p and q, we also denote ei = [p; q].
17


Definition 2.1.2 ([4]). The edge sequence which is passed by a
shortest path is called the shortest sequence.
Each face has two-dimensional coordinate system associated with
0

it. If faces f and f are adjacent sharing edge e; then define the planar
0

unfolding of face f onto face f as follows.
0


Definition 2.1.3 ([4]). Given two adjacent faces f and f , the planar
0

0

unfolding of face f onto face f is the image of points of f when rotated
0

about the line through e into the plane of f such that the points of f fall
on the opposite side of e to points of f. Points in the planar unfolding of
0

f onto f are written in the coordinate system of face f:

0

Figure 2.2: The unfolded image of f onto face f.

Assume that F = (f1; f2; : : : ; fm+1) is a sequence adjacent faces associated with an edge sequence E = (e1; e2; : : : ; em). The notion of planar
unfolding is extended to F as follow: Unfold f1 around e1 onto f2, unfold f1
and f2 around e2 onto f3, continue in this way until all faces f1; f2; : : : ; fm lie
is the plane of fm+1. Upon finishing, the planar unfolding along E rep-resents
points of faces f1; f2; : : : ; fm in the coordinate system of face fk+1. The
procedure of unfolding this sequence can be described as

18


Procedure 1 Planar unfolding
Require: A sequence of adjacent faces F = (f1; f2; : : : ; fm+1).

Ensure: Points of f1; f2; : : : ; fm in the coordinate system of face fm+1.
1: F := f1
2: for i := 1 to m do
3:

Rotate F around ei until F lies on the plane of fi+1
and lies on different sides of ei

4:

F := F [ fi+1

Remark 2.1.4. The order of unfolding a sequence of adjacent faces
can be reversed, i.e. we can unfold fm+1; fm; : : : ; f2 onto the plane of f1.
In fact, when implementing Chen and Han’s algorithm, Kaneva and
O’Rourke [5] did it.
The following properties of planar unfolding technique are well known.

Remark 2.1.5. Suppose that is a path along the sequence of triangles.
Then, the length of is conserved in the planar unfolding technique.
Remark 2.1.6. Because the length of a path is conserved after being
unfolded, the internal angles of points on a path are conserved in the
planar unfolding technique.
2.1.3

Properties of shortest paths on convex polyhedral surfaces

Denote S is the surface of a polyhedron. Before stating some
properties of shortest paths joining two points of a polyhedron, we
recall the concept of a shortcut for a path near a point of . If there is a

path, say joining w1 and w2 in the region P such that the new path in
which the path through w1; p, and w2 is replaced by is strictly shorter than
; then is called a shortcut for near p:

Property 2.1.7 ([8]). (i) A shortest path on S does not traverse any face
of P more than once; that is, the intersection of with any face f of S
is a line segment.
19


(ii)

A shortest path never crosses a vertex of v (but it may start of end
at a vertex).

(iii) For any three distinct points a; b; c 2 S, either one of the shortest paths

(a; b); (a; c) is a subpath of the other, or these two paths meet only
at a. In other words, two shortest paths from the same source point s
cannot intersect each other except at s and, if they have the same
destination point, possibly at that point too.
(iv)

If traverse the edge sequence E, then the unfolded image
straight line segment.

0

is a


Proof. (i) Suppose the contrary, traverses a face f of P more than once.
Let (a; b) consist of the segments 0; : : : ; n. There exists two portions i
and j, i < j; of in f. Let denote
closed segment [c; d]. Since
line segment [a; d] f. On the
every portion of is also a

by a closed segment [a; b], denote j by a
f is convex, the shortest path (a; b) is the
other hand, since is a shortest path then
shortest path joining two points. Then

i

shortest path from a to d is i [ i+1 [ [ j. Therefore [a; d] = i [ i+1 [ [ j,
contradicting the fact that i 6= j.
(ii) Suppose the contrary, let v be a vertex of S lying on a shortest path
(s; t), v 6= s and v 6= t. Let e1; e2 be the two edges of (s; t) incident on v.
Let F = ff1; f2; : : : ; fmg be the set of triangles containing v as a vertex, and
i be the internal angle of the triangle fi at the vertex v: Because the
polyhedron is convex, then the total vertex angle (v) of v is given by
m
X

(v) =

i=1

i< 2 :


Denote the left and right curve angle of at v by l(v) and r(v), respectively. We have l(v) + r(v) = (v) < 2 . Hence, at least one of l(v) and r(v)
less than . Without loss of generality, suppose that l(v) < : Denote by fk;
fk+1; : : : ; fk+r the faces which make the left curve angle of (s; t) at v.
We unfold the sequence of triangles S = (fk; fk+1; : : : ; fk+r) onto the face
fk+r (see Figure 2.3). Let the image of e1 be e1. The image of the sequence
forms a simple polygon S in which v is its vertex. Let g0; g1; : : : ; gr
20


Figure 2.3: A shortcut near v if

(s; t) pass through vertex v.

be boundary edges of S not incident on v and hi be the distance from v
to gi, i = 0; 1; : : : ; r. Set " := minfhi; i = 0; 1; : : : ; r g. It follows that the
intersections of the circle B(v; ") with e1; e2 exist. Let w1; w2 be these
intersections. l(v) < yeilds [w1; w2] S. Since e1; e2 are not collinear, [w1;
w2] is strictly shorter than the polyline w1vw2. Thus, there is a strictly
shorter path from s to b via a shortcut near v, a contradiction to (s; t)
being a shortest path.
(iii) Suppose the contrary, (a; b) and (a; c) first meet at v, v 2= fa; b; cg.
Then the length of the initial portion of (a; b) up to v equals the length
of the initial portion of (a; c) up to v. (Because if not then either (a; b) or
(a; c) can be shortened, this contradicts the fact that (a; b) and (a; c) are
shortest paths.) Therefore, a path consists of the initial portion of (a; c)
up to v and the second portion of (a; b) from v up to b, denoted by
0

(a; b), is also a shortest path from a to b.


Let (a; b) consist of the segments 0; : : : ; n. Let (a; c) consist of the
0
0
0
segments 0 ; : : : ; m . There exists i; j, 0 i n; 0 j m, such that v 2 i \ j .
Then, similar to case (ii), we can take a shortcut near v (see Figure 2.4)
0
0
and (a; b) can be shortened, contradicting the fact that (a; b) is a
shortest path. Therefore, (a; b) and (a; c) cannot meet.
(iv) Let f0; f1; : : : ; fn be the sequence of adjacent faces of S through whichs

passes, where ei = fi 1 \ fi; i = 1; : : : ; n
1. Let
consists of segments
0; : : : ; n. For each i = 1; : : : ; n unfold fi 1 onto fi about the line through ei
0
so as to make them coincident. Let i 1 be the unfolded image of i 1.
0
Since is the shortest possible, two segments i 1 and i must be
21


Figure 2.4: A shortcut near v if

(a; b) and (a; c) meet at v.

collinear in this common plane, and the angles which they form with ei
must therefore be equal. Now unfold the collection of faces f0; : : : ; fn
so as make them all lie in the same plane of fn. The required path is

then simply a straight line segment.

2.2

Chen and Han’s algorithm

In this section, we present Chen and Han’s algorithm for solving
Problem 1.
2.2.1

Projection technique

Given a sequence of adjacent face F = (f1; f2; : : : ; fm+1), and given a
source point s which is a vertex of f1 and not belong to e1 = f1 \ f2. After
unfolding F, all faces are unfolded into a common plane of fm+1. The
shortest path passing through these faces should be unfolded into a
straight line segment (Property 2.1.7). Let fi be the images of fi, i =
1; : : : ; m, ei be the images of ei, i = 1; : : : ; m, s be the image of s.
Definition 2.2.1 ([4]). The projection of the source image s on edge ei
s

is a closed segment, denoted by P roj , such that the shortest path from
ei

s

s to any point t 2 P rojei

line segment. Namely, we can connect s and t with a straight line
segment which crosses only the edge e1; e2; : : : ; ei 1 (see Figure 2.5).

Definition 2.2.2 ([4]). The set of points t of fi such that the straightest
geodesic from s to t intersects P roj

e

i 1

22