Luận án Đường ngắn nhất dọc theo một dãy các đoạn thẳng và bao lồi trực giao liên thông

Consider the case b /∈ [yj, yj+1] (and so yj 6= b) for all j = n, . . . , k. Let
y′n, . . . , y
′
k+1 be points defined as in the first part of the proof. Set
θn−1 := ∠(xn−1 − b, y′n − b)
26
and for n ≤ j ≤ k,
θj := ∠(xn−1 − b, y′n − b) + ∠(y′n − b, y′n+1 − b) + · · ·+ ∠(y′j − b, y′j+1 − b).
We have θk = θ ≥ pi. Let
r = min{j ≥ n : θj ≥ pi}.
As b /∈ [yr, yr+1],
0 < ∠(y′r − b, y′r+1 − b) = ∠(yr − b, yr+1 − b) < pi
and there exists
y∗′ ∈ ]y′r, y′r+1]
such that
θr−1 + ∠(y′r − b, y∗′ − b) = pi.
Let y∗ ∈ ]yr, yr+1] satisfy
‖y∗ − yr‖ = ‖y∗′ − y′r‖
and τ ∗ ∈ ]τ¯r, τ¯r+1] satisfy
η(τ ∗) = y∗.
Since b ∈ ]xn−1, y∗′[ , by Lemma 1.7(c)
γ ∗ [b, y∗′] is anSP (a, y∗′)(e1,...,en).
Thus
l
(
η|[τ0,τ∗]
)
= l
(
η|[τ0,τ¯n]
)
+ ‖yn − yn+1‖+ · · ·+ ‖yr−1 − yr‖+ ‖yr − y∗‖
= l
(
η|[τ0,τ¯n]
)
+ ‖y′n − y′n+1‖+ · · ·+ ‖y′r−1 − y′r‖+ ‖y′r − y∗′‖
≥ l(γ ∗ [b, y∗′]) = l(γ) + ‖b− y∗′‖ = l(γ) + ‖b− y∗‖.
Hence
l(η) ≥ l(η|[τ0,τ∗])+ ‖y∗ − q‖
≥ l(γ) + ‖b− y∗‖+ ‖y∗ − q‖
≥ l(γ) + ‖b− q‖
= l(γ ∗ [b, q]).
2
Theorem 1.2 gives a step-by-step method to check whether a path with
respect to a sequence of line segments is shortest: we just measure the angles
27
between line segments of the path and eis at points of intersection, from the
starting point to the terminating point.
We now consider several consequences of Theorem 1.2. In computational
geometry, edges of polygons intersect at their common endpoints. In such
cases, Theorem 1.2 reduces to the following simple form.
Corollary 1.5 Let E = (e1, . . . , ek) be a sequence of line segments and γ([t0, t1])
an SP (a, b)(e1,...,en−1) corresponding to xi = γ(t¯i) ∈ ei (1 ≤ i ≤ n − 1) and
n ≤ k. Suppose that b is the common endpoint of non-singleton line seg-
ments en = [b, bn],. . . , ek = [b, bk], and that xn−1 6= b (if n = 1, x0 := a). Let
q ∈ E, q 6= b. Then γ ∗ [b, q] is an SP (a, q)E iff θ ≥ pi, where
θ := ∠(xn−1 − b, bn − b) +
k−1∑
j=n
∠(bj − b, bj+1 − b) + ∠(bk − b, q − b).
Applying Corollary 1.5 we can prove the following result in [53]:
A shortest path joining two points on the surface of a convex polyhedron
D ⊂ R3 cannot pass through any vertex of D.
Indeed, suppose a shortest path γ on the surface S of D joins a and b on S
and goes through a vertex v ∈ S. As γ can be seen as a shortest path with
respect to a sequence of line segments, by Corollary 1.5, both the angle to
the left and the angle to the right of γ at v are not less than pi. Hence the
angle of D at v is not less than 2pi, a contradiction. Notice that the proof
still holds for polyhedrons D whose angle at every vertex is strictly less than
2pi.
Let us consider an example. Given a, q ∈ R3 \ {0}, we show that
γ = [a,0] ∗ [0, q]
is the shortest path that joins a with q and meets the x-, y-, and z-axes.
Suppose η is any path joining a and q and meets x-, y-, and z-axes at u, v, and
w, respectively. If one of the points u, v, w is coincident with b := 0 = (0, 0, 0),
then clearly l(γ) ≤ l(η). Assume that
b /∈ {u, v, w}
and that
η is anP (a, q)([b,v],[b,u],[b,w]).
28
Since
∠(a− b, v − b) + ∠(v − b, u− b) + ∠(u− b, w − b) + ∠(w − b, q − b) ≥ pi,
Corollary 1.5 says that, in the family of all P (a, q)([b,v],[b,u],[b,w]), l(γ) ≤ l(η).
Corollary 1.6 Suppose γ
(
[t0, t1]
)
is an SP (a, b)(e1,...,en) corresponding to xi =
γ(t¯i) ∈ ei, 1 ≤ i ≤ n, xn 6= b. Let y ∈ en, y 6= xn, and let q be any point in E
such that q 6= xn and ∠(y−xn, q−xn) = ∠(y−xn, b−xn). Then γ|[t0,t¯n]∗ [xn, q]
is an SP (a, q)(e1,...,en). In particular, if we rotate the last line segment [xn, b]
about the line containing en, we then get a new shortest path with respect to
a sequence of line segments.
Proof. Set x0 := a. If x0 = x1 = · · · = xn, then there is nothing to prove.
So we assume that m = max{i : xi 6= b} exists. By Theorem 1.2, for any
yi ∈ ei, yi 6= xn, m+ 1 ≤ i ≤ n,
∠(xm−xn, ym+1−xn) +∠(ym+1−xn, ym+2−xn) + · · ·+∠(yn−xn, b−xn) ≥ pi.
Hence
∠(xm − xn, ym+1 − xn) + · · ·+ ∠(yn − xn, q − xn) ≥ pi
since
∠(yn − xn, q − xn) = ∠(yn − xn, b− xn).
Applying Theorem 1.2 once more, we find that
γ|[t0,t¯n] ∗ [xn, q] is anSP (a, q)(e1,...,en).
2
Corollary 1.7 Let γ([t0, t1]) be an SP (a, b)(e1,...,en) corresponding to xi =
γ(t¯i) ∈ ei, 1 ≤ i ≤ n. Set x0 := a, xn+1 := b. Suppose also that for
some j, ej is non-singleton, xj−1 6= xj, and xj+1 6= xj.
(a) If yj ∈ ej, yj 6= xj, then θ := ∠(xj−1−xj, yj−xj)+∠(yj−xj, xj+1−xj) ≥ pi.
In particular, if xj is an interior point of ej, then θ = pi.
(b) Let L be the line containing ej. If xj−1 ∈ L and xj+1 /∈ L, then xj is an
end point of ej with ‖xj−1 − xj‖ = minx∈ej ‖xj−1 − x‖ and θ > pi. The
case xj+1 ∈ L and xj−1 /∈ L is similar.
(c) If xj−1, xj+1 ∈ L, then either ∠(xj−1 − xj, xj+1 − xj) = pi or ∠(xj−1 −
xj, yj − xj) = ∠(xj+1 − xj, yj − xj) = pi, where yj ∈ ej, yj 6= xj. In the
latter case xj is an end point of ej with ‖xj−1− xj‖ = minx∈ej ‖xj−1− x‖.
29
Proof. (a) Applying Theorem 1.2 to γ|[t0,t¯j+1] (t¯n+1 := t1) and the sequence
e1, . . . , ej, we get θ ≥ pi. If xj is an interior point of ej, take y′j ∈ ej such that
xj is an interior point of [yj, y
′
j].
We then also have
θ′ := ∠(xj−1 − xj, y′j − xj) + ∠(y′j − xj, xj+1 − xj) ≥ pi.
Since θ + θ′ = 2pi, θ = θ′ = pi.
(b) Suppose xj−1 ∈ L and xj+1 /∈ L. Since θ 6= pi, θ > pi and according to
part (a)
xj must be an endpoint.
If ‖xj−1 − xj‖ > minx∈ej ‖xj−1 − x‖, there exists x¯ ∈ ej with
‖xj−1 − xj‖ > ‖xj−1 − x¯‖, i.e., x¯ ∈ [xj−1, xj[ .
Since xj+1 /∈ L
‖xj−1−xj‖+‖xj−xj+1‖ = ‖xj−1−x¯‖+‖x¯−xj‖+‖xj−xj+1‖ > ‖xj−1−x¯‖+‖x¯−xj+1‖,
i.e.,
l
(
γ|[t¯j−1,t¯j+1]
)
> l
(
[xj−1, x¯] ∗ [x¯, xj+1]
)
,
a contradiction. Thus
‖xj−1 − xj‖ = min
x∈ej
‖xj−1 − x‖.
(c) If xj ∈ ]xj−1, xj+1[ , then
∠(xj−1 − xj, xj+1 − xj) = pi.
Otherwise, say xj−1 ∈ ]xj, xj+1], an analysis which is similar to that in part
(b) shows that
xj is an end point of ej
with
‖xj−1 − xj‖ = min
x∈ej
‖xj−1 − x‖
and
∠(xj−1 − xj, yj − xj) = ∠(xj+1 − xj, yj − xj) = pi, for yj ∈ ej, yj 6= xj.
2
The following result is a converse of Corollary 1.7 and it gives sufficient
conditions for a path with respect to a sequence of line segments to be short-
est.
30
Corollary 1.8 Let E = (e1, . . . , en) be a sequence of line segments and γ([t0, t1])
an SP (a, b)(e1,...,en−1) corresponding to xi = γ(t¯i) ∈ ei, 1 ≤ i ≤ n−1. Let b ∈ en
and q ∈ E, q 6= b. Set x0 = a and suppose that m = max{i : xi 6= b} exits
and that there is y ∈ en, y 6= b.
(a) If θ := ∠(xm−b, y−b)+∠(y−b, q−b) = pi, then γ ∗ [b, q] is an SP (a, q)E.
(b) If b is an end point of en and θ > pi, then γ ∗ [b, q] is an SP (a, q)E.
Proof. (a) For any y′ ∈ en, y′ 6= b, we always have
∠(xm − b, y′ − b) + ∠(y′ − b, q − b) = pi.
Thus by Theorem 1.2
γ ∗ [b, q] is anSP (a, q)(e1,...,em,en).
If m < n− 1, it follows from Lemma 1.6(b) that
γ ∗ [b, q] is anSP (a, q)E .
(b) follows directly from Corollary 1.5. 2
To illustrate Corollaries 1.7 and 1.8 let us consider a triangle in R2 having
acute angles (Figure 1.4). For u ∈ e1 fixed, Corollary 1.8 states that the
triangle uvw has minimum perimeter because angles θ at v and w are pi.
Figure 1.4 shows that
∠(w − u, z1 − u) + ∠(z1 − u, v − u) 6= pi.
Since the angles at u do not satisfy Corollary 1.7(a), uvw is not the inscribed
triangle with minimum perimeter.
Figure 1.4: SP (u, u)(e1,e2,e3) = [u, v] ∗ [v, w] ∗ [w, u]
We hope that some results in this chapter could be used to study Steiner’s
problem (see [55]): Given a convex polygon in the plane, find an inscribed
31
polygon of minimal perimeter.
We are now in a position to consider the general case of concatenation of
two shortest paths with respect to two sequences of line segments. Roughly
speaking, the following theorem says that if the last line segment of a shortest
path with respect to a sequence of line segments and the first of the other
overlap, the two paths can be joined to become a shortest path with respect
to sequence of line segments.
Theorem 1.3 Let E = (e1, . . . , ek) be a sequence of line segments. Suppose
that γ1([t0, t1]) is an SP (a, b)(e1,...,en−1) and γ2([t
∗, t2]) is an SP (c, d)(en,...,ek),
where t∗ < t1 < t2, and γ1(t1) = γ2(t1) = b. Suppose also that γ1, γ2 satisfy
assumption (A). If t1 ≤ t¯n ≤ · · · ≤ t¯k ≤ t2, xi := γ2(t¯i) ∈ ei for n ≤ i ≤
k, and if there exists  > 0 such that γ1([t1 − , t1]) ⊂ γ2([t∗, t1]), then the
concatenation γ of γ1 and γ2|[t1,t2] is an SP (a, d)E.
Figure 1.5: Illustration of Theorem 1.3 (γ1([t1 − , t1]) ⊂ γ2([t∗, t1]))
Proof. Let t0 =: t¯0 ≤ t¯1 ≤ · · · ≤ t¯n−1 ≤ t1,
xi := γ1(t¯i) ∈ ei for i = 1, . . . , n− 1,
x0 := γ1(t¯0) = a.
We can also assume, by applying Lemma 1.7 if necessary, that b = xn ∈ en,
i.e., t¯n = t1. Set t¯k+1 := t2 and note that γ is a P (a, d)E . The proof is divided
into two cases.
Case 1: All ej, j ≥ n, are non-singleton. Set
xk+1 := γ2(t¯k+1) = d,
m = max{i < n : xi 6= b},
r = min{j > n : xj 6= b}.
32
m and r exist due to assumption (A) and Theorem 1.1. Assume that
c ∈ [xm, b[ .
Then, by Lemma 1.2
γ2|[t∗,t¯r] = [c, b] ∗ [b, xr]
is an SP (c, xr)(en,...,er−1). Applying Theorem 1.2 to γ2|[t∗,t¯r] we find that
all angles θ at b are not less thanpi.
Thus this theorem also says that
γ1 ∗ γ2|[t1,t¯r] = γ1 ∗ [b, xr]
is an SP (a, xr)(e1,...,em,en,...,er−1). If m < n− 1, Lemma 1.6 again shows that
γ1 ∗ γ2|[t1,t¯r]
is an SP (a, xr)(e1,...,er−1). We continue in this fashion to obtain, after a finite
number of times, that
γ is anSP (a, d)E .
Case 2: The line segment ej is a singleton for some j ≥ n. The particular
case when en is a singleton, i.e., en = {b}, is derived immediately from the
following lemma.
Lemma 1.8 Let ζ([α0, α1]) be a P (p, u)(e1,...,el) and ξ([α1, α2]) a
P (u, q)(el+1,...,em). Then ψ = ζ ∗ ξ is an SP (p, q)(e1,...,el,{u},el+1,...,em) iff ζ is an
SP (p, u)(e1,...,el) and ξ an SP (u, q)(el+1,...,em).
Proof. Indeed, if ψ is a shortest path with respect to the sequence e1, . . . , el, {u}, el+1,
then so are ζ and ξ (Lemma 1.2). Conversely, suppose ζ and ξ are short-
est paths. Let η([τ0, τ1]) be any P (p, q)(e1,...,el,{u},el+1,...,em), corresponding to
yi = η(τ¯i) ∈ ei, i = 1, . . . ,m, and η(τ¯u) = u (τ¯l ≤ τ¯u ≤ τ¯l+1). Since
η|[τ0,τ¯u] is anP (p, u)(e1,...,el)
and
η|[τ¯u,τ1] is anP (u, q)(el+1,...,em),
l(η) = l
(
η|[τ0,τ¯u]
)
+ l
(
η|[τ¯u,τ1]
) ≥ l(ζ) + l(ξ) = l(ψ).
Therefore ψ is an SP (p, q)(e1,...,el,{u},el+1,...,em).
33
We now prove the theorem for the case
s = min{j ≥ n : ej is a singleton} > n,
say es = {u}. If t1 = t¯n+1 = · · · = t¯s, then
b = u ∈ en+1 ∩ · · · ∩ es
and by Lemma 1.5
γ1 is also anSP (a, b)(e1,...,es−1)
and
γ2|[t1,t2] anSP (b, d)(es+1,...,ek).
Lemma 1.8 above states that
γ is anSP (a, d)(e1,...,ek).
If t¯s > t1, by Case 1 we find that
γ˜ = γ1 ∗ γ2|[t1,t¯s] is anSP (a, u)(e1,...,es−1).
We then apply Lemma 1.8 again to
γ˜ and γ2|[t¯s,t2]
to obtain the required result. The proof of the theorem is complete. 2
If the last line segment of a shortest path with respect to a sequence of line
segments and the first of the other do not overlap, we can use the following.
Corollary 1.9 Suppose γ1([t0, t1]) is an SP (a, b)(e1,...,en) and γ2([t1, t2]) is an
SP (b, c)(en+1,...,ek), t0 < t1 < t2. Suppose also that γ1, γ2 satisfy assumption
(A). Then γ = γ1 ∗ γ2 is an SP (a, c)(e1,...,ek) iff there exists  > 0 such that
γ1|[t1−,t1]∗γ2|[t1,t1+] is a shortest path with respect to the sequence e1, e2, . . . , en.
Loosely speaking, if the last segment of the first shortest path and the first
segment of the second form a shortest path, then their concatenation is also
a shortest path.
Proof. If γ = γ1 ∗ γ2 is an SP (a, c)(e1,...,ek), then
ζ := γ1|[t1−,t1] ∗ γ2|[t1,t1+] = γ|[t1−,t1+]
is a shortest path with respect to some sequence of line segments for each
 ≤ min{t1− t0, t2− t1} (Lemma 1.2). Conversely suppose that ζ is a shortest
34
path with respect to some sequence of line segments and satisfies assumption
(A). Since
γ1|[t1−,t1] = ζ|[t1−,t1],
applying Theorem 1.3 to γ1 and ζ we find that ξ = γ1 ∗ ζ|[t1,t1+] is a shortest
path with respect to some sequence of line segments. Applying Theorem 1.3
again to ξ and γ2 we obtain that
γ = ξ ∗ γ2|[t1+,t2]
is an SP (a, c)(e1,...,ek). 2
An et al. [13] and Hoai et al. [34] used a direct multiple shooting method
to approximate shortest paths in a simple polygon in R2 and on surfaces of
convex polytopes in R3. They divided the given region into subregions, found
a shortest path in each subregion and then “glued” them. They applied one
straightness condition, a version of Corollary 1.9, to adjust the paths to get
better aproximations.
1.3 Conclusions
We present the existence and uniqueness of the shortest path (Theorem
1.1 and Corollary 1.2). We then investigate some characteristics of angles
between the shortest path and line segments eis, especially when the path
goes through common points of eis. Theorem 1.2 and Corollaries 1.7–1.8 give
a step-by-step method to determine whether a path is shortest. Sufficient
conditions under which concatenation of two shortest paths is shortest are
also given (Theorem 1.3 and Corollary 1.9).
35
Chapter 2
Straightest Paths on a Sequence of
Adjacent Polygons
Back to the shortest path problems, as we know, a line segment is the
shortest path joining its two endpoints in 3D space. A very common technique
is unfolding. Many researchers use it to solve the shortest path subproblem
between two points on a sequence of triangles. If we can draw a line segment
between two images inside the simple polygon after unfolding the sequence
of triangles, then the inverse image of this line segment is the shortest path
joining two given points. The question is how to find this shortest path
without unfolding? Under the idea of the straightest geodesic of Polthier and
Schmies [49] and the thought of answering the above question, we come to
the definition of straightest paths.
The present chapter is written on the basis of the paper [32] in the List of
Author’s Related Papers on page 72 of this dissertation.
2.1 Straightest Paths
In [49] Polthier and Schmies presented a new concept of geodesics: straight-
est geodesics are paths that have equal path angle on both sides at each point.
In this section we consider “straightest paths” which are slightly differ from
the original and in fact are particular shortest paths with respect to some
sequence of line segments. Let S = (f1, f2, . . . , fk+1) be a sequence of (not
necessary distinct) adjacent convex polygons in R2 or R3, then
ei := fi ∩ fi+1 is an edge for 1 ≤ i ≤ k.
36
Definition 2.1 A straightest path γ : [t0, t1]→ ∪k+1i=1 fi on the sequence S is a
path that satisfies assumption (A) and the following conditions:
(a) there exist integers 1 ≤ m ≤ n ≤ k and a sequence of numbers
t0 =: t¯m−1 < t¯m ≤ · · · ≤ t¯n < t¯n+1 := t1
such that
xi := γ(t¯i) ∈ ei form ≤ i ≤ n
and
xm−1 := γ(t0) ∈ fm, xn+1 := γ(t1) ∈ fn+1;
(b) l
(
γ|[t¯i,t¯i+1]
)
= ‖xi − xi+1‖ for m− 1 ≤ i ≤ n;
(c) For zi ∈ ei, zi 6= xi, we have
∠(xi−1 − xi, zi − xi) + ∠(zi − xi, xi+1 − xi) = pi
if xi ∈ ei is not a common vertex, and
∠(xi∗−1− xi, zi∗ − xi) +
r−1∑
j=i∗
∠(zj − xi, zj+1− xi) +∠(zr− xi, xr+1− xi) = pi
if xi∗−1 6= xi∗ = xi∗+1 = · · · = xr 6= xr+1 and i∗ ≤ i ≤ r.
It is conventional to define straightest path joining a with b on the same
polygon (with respect to an empty sequence of common edges) to be any
path that joins a with b, one-to-one, and has length ‖a− b‖, i.e., a SP (a, b)∅.
Figure 2.1: Straightest path γ from f2 to f9 on a sequence S =
⋃i=10
i=1 fi
37
Condition (a) states that a straightest path is a path with respect to
the sequence em, em+1, . . . , en. Condition (b) and Lemma 1.1 imply that
γ([t¯i, t¯i+1]) = [xi, xi+1] ⊂ fi+1 for m − 1 ≤ i ≤ n. We observe also that
condition (c) does not depend on the choice of zi ∈ ei, m ≤ i ≤ n. Corol-
lary 1.8 and Theorem 1.2 show that γ is an SP (xm−1, xn+1)(em,...,en). Note
also that assumption (A), the conditions t0 < t¯m, t¯n < t1, and (b) imply
that x0 6= x1 and xn 6= xn+1. These conditions do not restrict the definition
of straightest paths since if x0 belongs to a common edge then we choose
m = max{j : x0 ∈ fj}. Similarly, we can assume that xn+1 does not belong
to en.
There are reasons why we study straightest paths: First the shortest path
joining two given points on the surface of a convex polyhedron D ⊂ R3 does
not go through any vertex of D (see [53], Lemma 4.1). Thus, by Corollary
1.7, the path is straightest. Second, every shortest path with respect to
some sequence of line segments joining two points on a surface S consisting
of convex polygons is composed of straightest paths joining vertexes of S
(Proposition 2.1).
2.2 An Initial Value Problem on a Sequence of Adja-
cent Polygons
Here we recall the problem of an initial value problem in differential equa-
tions (see [25], p. 1).
Problem. To find a differentiable function ϕ difined on a real interval I such
that
(i) (t, ϕ(t)) ∈ D (t ∈ I)
(ii) ϕ′(t) = f(t, ϕ(t)))
(
t ∈ I,′= d
dt
)
This problem is called an ordinary differential equation of the first order.
With the straightest paths, we have also a similar initial value problem as
follows.
Let γ([t0, t1]) be a straightest path on S = (f1, f2, . . . , fk+1), γ(t0) ∈ fm,
and v a nonzero vector that is parallel to fm. If there exists t
∗ > t0 such that
γ([t0, t
∗]) ⊂ fm
38
and
γ(t∗)− γ(t0) = λv for someλ > 0
we say that γ starts at γ(t0) in the direction of v.
Theorem 2.1 (An initial value problem) Let S = (f1, f2, . . . , fk+1) be a se-
quence of adjacent convex polygons. Let a, p ∈ fm, a 6= p, and v = p − a.
Then there exists a unique longest straightest path γ([t0, t1]) on S starting at
a and in the direction of v. Moreover, if η([τ0, τ1]) is any straightest path
on S starting at a and in the direction of v, then η equals γ|[t0,t∗] for some
t0 ≤ t∗ ≤ t1. Thus every straightest path on S can be extended to a longest
straightest path.
Proof. There is nothing to prove if k = 0, S = {f1}. Thus we assume,
without loss of the generality, that k ≥ 1, a, p ∈ f1, and a /∈ f2.
First we construct γ. Denote ei = fi ∩ fi+1, i = 1, . . . , k. Set
t0 = 0 and t¯1 = max{t : a+ tv ∈ f1}.
Since p = a+ v ∈ f1, t¯1 ≥ 1. Define
γ1 : [0, t¯1]→ f1
by
γ1(0) = aγ1(t¯1) = x1 := a+ t¯1v ∈ f1,
and
γ1 is affine on [0, t¯1].
If x1 /∈ e1 we put t1 := t¯1 and γ := γ1.
Suppose x1 ∈ e1. Choose any z1 ∈ e1, z1 6= x1. If there exists p1 ∈ f2 such
that
∠(a− x1, z1 − x1) + ∠(z1 − x1, p1 − x1) = pi, (2.1)
set
v1 := p1 − x1, σ1 := max{t : x1 + tv1 ∈ f2} ≥ 1, t¯2 := t¯1 + σ1,
and
x2 := x1 + σ1v1 ∈ f2.
We then define
γ2 : [t¯1, t¯2]→ f2
39
by
γ2(t¯1) = x1, γ2(t¯2) = x2,
and
γ2 is affine on [t¯1, t¯2].
Clearly γ1 ∗ γ2 is a straightest path starting at a, in the direction of v, and
joining a with x2. Observe that such a p1 always exists if x1 is an interior
point of e1.
Suppose x1 is an endpoint of e1 and there is no p1 ∈ f2 satisfying (2.1). If
x1 is not a common vertex of e1 and e2, set
t1 := t¯1 and γ := γ1.
Assume that x1 is a common vertex of e1 and e2. Let
r := max{i : x1 ∈ ej, 1 ≤ j ≤ i}.
Choose
zj ∈ ej, zj 6= x1, 1 ≤ j ≤ r,
and let z∗r+1 be a point on the second edge of fr+1 that has an endpoint x1
and z∗r+1 6= x1. Let
θ1 :=∠(a− x1, z1 − x1) + ∠(z1 − x1, z2 − x1)
+ · · ·+ ∠(zr−1 − x1, zr − x1) + ∠(zr − x1, z∗r+1 − x1).
We call θ1 the angle of incidence at x1. If θ1 < pi, set
t1 := t¯1 and γ := γ1.
Assume θ1 ≥ pi. Put
s := max
{
i : ∠(a−x1, z1−x1)+∠(z1−x1, z2−x1)+· · ·+∠(zi−1−x1, zi−x1) < pi
}
.
Since there is no p1 ∈ f2 satisfying (2.1), 2 ≤ s ≤ r and there exists ps ∈
fs+1 \ fs, such that
∠(a− x1, z1 − x1) + ∠(z1 − x1, z2 − x1) + · · ·+ ∠(zs − x1, ps − x1) = pi.
Set t¯2 = · · · = t¯s := t¯1, x2 = · · · = xs