Luận án Shortest paths along a sequence of line segments and connected orthogonal convex hulls

VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY
INSTITUTE OF MATHEMATICS
PHONG THI THU HUYEN
SHORTEST PATHS ALONG A SEQUENCE OF
LINE SEGMENTS AND
CONNECTED ORTHOGONAL CONVEX HULLS
DISSERTATION
SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE DEGREE OF
DOCTOR OF PHILOSOPHY IN MATHEMATICS
HANOI - 2021
VIETNAM ACADEMY OF SCIENCE AND TECHNOLOGY
INSTITUTE OF MATHEMATICS
PHONG THI THU HUYEN
SHORTEST PATHS ALONG A SEQUENCE OF
LINE SEGMENTS AND
CONNECTED ORTHOGONAL CONVEX HULLS
Speciality: Applied Mathematics
Speciality code: 9 46 01 12
DISSERTATION
SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
FOR THE DEGREE OF
DOCTOR OF PHILOSOPHY IN MATHEMATICS
Supervisor: Associate Professor PHAN THANH AN
HANOI - 2021
Confirmation
This dissertation was written on the basis of my research works carried out at
Institute of Mathematics, Vietnam Academy of Science and Technology, un-
der the supervision of Associate Professor Phan Thanh An. All the presented
results have never been published by others.
September 17, 2021
The author
Phong Thi Thu Huyen
i
Acknowledgment
First and foremost, I would like to thank my academic advisor, Associate
Professor Phan Thanh An, for his guidance and constant encouragement.
The wonderful research environment of the Institute of Mathematics, Viet-
nam Academy of Science and Technology, and the excellence of its staff have
helped me to complete this work within the schedule. I would like to express
my special appreciation to Professor Hoang Xuan Phu, Professor Nguyen
Dong Yen, Associate Professor Ta Duy Phuong, and other members of the
weekly seminar at Department of Numerical Analysis and Scientific Com-
puting, Institute of Mathematics, as well as all the members of Associate
Professor Phan Thanh An’s research group for their valuable comments and
suggestions on my research results. In particular, I would like to express
my sincere thanks to Associate Professor Nguyen Ngoc Hai and PhD student
Nguyen Thi Le for their significant comments and suggestions concerning the
research related to Chapters 1, 2 and Chapter 3 of this dissertation.
I would like to thank the Professor Nguyen Dong Yen, Doctor Hoang Nam
Dung, Doctor Nguyen Duc Manh, Doctor Le Xuan Thanh, Associate Profes-
sor Nguyen Nang Tam, Associate Professor Nguyen Thanh Trung, and Doctor
Le Hai Yen, and the two anonymous referees, for their careful readings of this
dissertation and valuable comments.
Finally, I would like to thank my family for their endless love and uncon-
ditional support.
ii
Contents
Table of Notation v
List of Figures vi
Introduction viii
Chapter 0. Preliminaries 1
0.1 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
0.2 Graham’s Convex Hull Algorithm . . . . . . . . . . . . . . . . 3
Chapter 1. Shortest Paths with respect to a Sequence of Line
Segments in Euclidean Spaces 9
1.1 Shortest Paths with respect to a Sequence of Ordered Line
Segments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.2 Concatenation of Two Shortest Paths . . . . . . . . . . . . . . 21
1.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
Chapter 2. Straightest Paths on a Sequence of Adjacent Poly-
gons 36
2.1 Straightest Paths . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.2 An Initial Value Problem on a Sequence of Adjacent Polygons 38
2.3 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
Chapter 3. Finding the Connected Orthogonal Convex Hull of
a Finite Planar Point Set 46
3.1 Orthogonal Convex Sets and their Properties . . . . . . . . . . 46
iii
3.2 Construction of the Connected Orthogonal Convex Hull of a
Finite Planar Point Set . . . . . . . . . . . . . . . . . . . . . . 56
3.3 Algorithm, Implementation and Complexity . . . . . . . . . . 60
3.3.1 New Algorithm Based on Graham’s Convex Hull Algo-
rithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
3.3.2 Complexity . . . . . . . . . . . . . . . . . . . . . . . . 66
3.3.3 Implementation . . . . . . . . . . . . . . . . . . . . . . 69
3.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
General Conclusions 71
List of Author’s Related Papers 72
iv
Table of Notations
(X, ρ) a metric space X with metric ρ
[t0, t1], t0, t1 ∈ R an interval in R
γ a path
l(γ) the length of a path γ
(E, ‖.‖) an Euclidean space E with norm ‖.‖
e1, e2, . . . , ek a sequence of line segments in E
a, b, c, p, q, . . . some points in spaces
[p, q], p, q ∈ E a line segment between two points p and q
xa, ya two coordinates of a point a = (xa, ya)
P (a, b)(e1,...,ek) a path joining a and b with respect to the
sequence e1, . . . , ek
SP (a, b)(e1,...,ek) a shortest path joining a and b with respect
to the sequence e1, . . . , ek
γ1 ∗ γ2 the concatenation of γ1 and γ2
σ : t0 = τ0 < τ1 < · · · < τn = t1 a set of partitions of [t0, t1]
`(a, b) an orthogonal line through a and b in the
sense of orthogonal convexity
s(a, b) an orthogonal line segment through a and
b in the sense of orthogonal convexity
F(K) the family of all connected orthogonal con-
vex hulls of the set K
P a planar finite point set
COCH(P ) the connected orthogonal convex hull of P
Pah the set of points in P in the quadrant of
`(a, b)
Pah a staircase path joining a and h
T (P ) an orthogonal convex (x, y)-polygon
o− ext(COCH)(P ) the set of extreme points of COCH(P )
v
List of Figures
0.1 Illustration of a simple polygon . . . . . . . . . . . . . . . . . 3
0.2 Illustration of convex sets . . . . . . . . . . . . . . . . . . . . 4
0.3 Illustration of a polytope . . . . . . . . . . . . . . . . . . . . . 4
0.4 Convex hull problem . . . . . . . . . . . . . . . . . . . . . . . 5
0.5 Illustration of a stack . . . . . . . . . . . . . . . . . . . . . . . 7
0.6 An illustration for Graham’s convex hull algorithm . . . . . . 7
1.1 Illustration of a path . . . . . . . . . . . . . . . . . . . . . . . 10
1.2 Illustration of Theorem 1.1 . . . . . . . . . . . . . . . . . . . . 17
1.3 Illustration of Theorem 1.2 . . . . . . . . . . . . . . . . . . . . 24
1.4 Illustration of Corollaries 1.7 and 1.8 . . . . . . . . . . . . . . 31
1.5 Illustration of Theorem 1.3 . . . . . . . . . . . . . . . . . . . . 32
2.1 Illustration for a straightest path . . . . . . . . . . . . . . . . 37
2.2 A counterexample for the existence of straightest paths . . . . 42
3.1 Orthogonal convex sets . . . . . . . . . . . . . . . . . . . . . . 47
3.2 Connected orthogonal convex hulls . . . . . . . . . . . . . . . 48
3.3 Orthogonal lines . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.4 Semi-isolated points . . . . . . . . . . . . . . . . . . . . . . . . 50
3.5 Two forms of an orthogonal convex set . . . . . . . . . . . . . 52
3.6 Example of the intersection of connected orthogonal convex sets 53
3.7 Illustration of Remark 3.1 . . . . . . . . . . . . . . . . . . . . 54
3.8 Corners of an orthogonal line . . . . . . . . . . . . . . . . . . 55
3.9 Maximal elements . . . . . . . . . . . . . . . . . . . . . . . . . 58
3.10 An extreme point . . . . . . . . . . . . . . . . . . . . . . . . . 59
vi
3.11 The orthogonal line determined by two points in the sense of
orthogonal convexity . . . . . . . . . . . . . . . . . . . . . . . 61
3.12 Left and four cases of orthogonal lines . . . . . . . . . . . . . 62
3.13 An example of Procedure Semi-Isolated−Point . . . . . . . . . 63
3.14 Illustration of the connected orthogonal convex hull algorithm 67
3.15 Illustration of time complexity . . . . . . . . . . . . . . . . . . 69
vii
Introduction
This dissertation studies shortest paths and straightest paths along a se-
quence of line segments in Euclidean spaces and connected orthogonal convex
hulls of a finite planar point set. They are meaningful problems in computa-
tional geometry.
Finding shortest paths (joining two given points, from a source point to
many destinations, from a point to a line segment, ...) in a geometric do-
main (such as on surface of a polytope, a terrain, inside a simple polygon,
...) is a classical geometric optimization problem and has many applications
in different areas such as robotics, geographic information systems and nav-
igation (see, for example, Agarwal et al. [2], Sethian [51]). To date, many
algorithms have been proposed to solve: touring polygons problems (see, for
example, Dror et al. [27], Ahadi et al. [3]), the shortest path problem on
polyhedral surfaces (see, for example, Mitchell et al. [41], [38], Chen and
Han [22], Varadarajan and Agarwal [59]), the weighted region problem (see,
for example, Aleksandrov et al. [8]), the shortest descending path problem
(see, for example, Ahmed et al. [4], [5], Cheng and Jin [24]), and the shortest
gentle descending path problem (see, for example, Ahmed et al. [6], Bose
et al. [19], Mitchell et al. [39], [40]). However, the problem of finding the
shortest path joining two points in three dimensions in the presence of gen-
eral polyhedral obstacles is known to be computationally difficult (see, for
example, Bajaj [16], Canny and Reif [21]).
In some shortest path problems, exact and approximate solutions are com-
puted based on solving a subproblem of finding the shortest path joining two
given points along a sequence of adjacent triangles (the adjacent triangles on
a polyhedral surface). Several algorithms need to concatenate of a shortest
path from a sequence of adjacent triangles with a line segment on a new
adjacent triangle (see, for example, Chen and Han [22], Cook [26], Balasub-
ramanian et al. [17], Cheng and Jin [23], Pham-Trong et al. [48], Xin and
viii
Wang [60], Tran et al. [56]). Not many properties of shortest paths on poly-
hedral surfaces have been shown (see, for example, Sharir and Shorr [53],
Mitchell et al., [41], Bajaj [16], Canney and Reif [21]). They usually sup-
pose paths as polylines. The properties of shortest paths along sequences of
adjacent triangles is even less than that (see Mitchell et al. [41]). But the
question is even more basic “Does the shortest path joining two points along
a sequence of adjacent triangles exist uniquely?”. The uniqueness of such
a path is assumed even in geodesical spaces and generalized segment spaces
(see Hai and An [31]). Thus, this question is important not only in compu-
tational respect but also in theoretical respect. In this dissertation, we will
consider the existence and uniqueness of such shortest paths. We show how
a shortest path bends at an edge, and moreover how two shortest paths can
“glue” together to form one shortest path.
In the dissertation, we consider the problem of finding the shortest path
between two points along a sequence of adjacent triangles in a general setting.
The sequence of triangles is replaced by a sequence of ordered line segments.
The 3D space is replaced by a Euclidean space. Let a, b be two points in
Euclidean space E and e1, e2, ..., ek ∈ E, finding the shortest path joining a
and b with re ... ollary 3.2), and its extreme vertices belong to the
given points (Proposition 3.6). We present a procedure to determine if a given
69
finite planar point set has the connected orthogonal convex hull. Section 3.3
contains the main algorithm, which is based on the idea of Graham’s convex
hull algorithm, for finding the connected orthogonal convex hull of a finite
planar point set (Algorithm 2) and it states that the lower bound of such
algorithm is O(n log n) (Proposition 3.8). Some numerical results show the
connected orthogonal convex hulls of some sets of a finite number of points
which is randomly positioned in the interior of a given square (Table 1).
70
General Conclusions
This dissertation applies different tools from convex analysis, optimization
theory, and computational geometry to study some constrained optimization
problems in computational geometry.
The main results of the dissertation include:
- the existence and uniquesness of shortest paths along a sequence of line
segments;
- conditions for concatenation of two shortest paths to be a shortest paths;
- straightest paths and longest straightest paths on a sequence of adjacent
triangles;
- a property of connected orthogonal convex hulls; the construction of the
connected orthgonal convex hull via extreme points;
- an efficient algorithm to finding the connected orthogonal convex hull of
a finite planar point set and an evaluating the time complexity for all
algorithms which find the connected orthogonal convex hull of a finite
planar point set.
71
List of Author’s Related Papers
[15 ] An, P.T., Huyen, P.T.T., Le, N.T.: A modified graham’s scan algorithm
for finding the connected orthogonal convex hull of a finite planar point
set. Applied Mathematics and Computation 397 (2021)
[32 ] Hai, N.N., An, P.T., Huyen, P.T.T.: Shortest paths along a sequence
of line segments in euclidean spaces. Journal of Convex Analysis 26(4),
1089–1112 (2019)
72
References
[1] Abello, J., Estivill-Castro, V., Shermer, T., Urrutia, J.: Illumination of
orthogonal polygons with orthogonal floodlights. International Journal
of Computational Geometry & Applications 8, 25–38 (1998)
[2] Agarwal, P.K., Har-Peled, S., Karia, M.: Computing approximate short-
est paths on convex polytopes. Algorithmica 33, 227–242 (2002)
[3] Ahadi, A., Mozafari, A., Zarei, A.: Touring a sequence of disjoint poly-
gons: Complexity and extension. Theoretical Computer Science 556,
45–54 (2014)
[4] Ahmed, M., Das, S., Lodha, S., Lubiw, A., Maheshwari, A., Roy, S.: Ap-
proximation algorithms for shortest descending paths in terrains. Journal
of Discrete Algorithms 8, 214–230 (2010)
[5] Ahmed, M., Lubiw, A.: Shortest descending paths: towards an exact
algorithm. International Journal of Computational Geometry & Appli-
cations 21, 431–466 (2011)
[6] Ahmed, M., Lubiw, A., Maheshwari, A.: Shortest gently descending
paths. In: WALCOM: Algorithms and Computation, Third International
Workshop, Lecture Notes in Computer Science, vol. 5431, pp. 59–70.
Springer (2009)
[7] Akl, S.G., Toussaint, G.T.: A fast convex hull algorithm. Information
Processing Letters 7 (1978)
[8] Aleksandrov, L., Maheshwari, A., Sack, J.R.: Determining approximate
shortest paths on weighted polyhedral surfaces. Journal of the ACM 52,
25–53 (2005)
[9] Allison, D.C.S., Noga, M.T.: Some performance tests of convex hull
algorithms. BIT Numerical Mathematics 24, 2–13 (1984)
73
[10] An, P.T.: Method of orienting curves for determining the convex hull of
a finite set of points in the plane. Optimization 59, 175–179 (2010)
[11] An, P.T.: Finding shortest paths in a sequence of triangles in 3d by the
method of orienting curves. Optimization 67(1), 159–177 (2017)
[12] An, P.T.: Optimization Approaches for Computational Geometry. Se-
ries of Monographs Application and Development of High-Tech. Vietnam
Academy of Science and Technology (2017)
[13] An, P.T., Hai, N.N., Hoai, T.V.: Direct multiple shooting method for
solving approximate shortest path problems. Journal of Computational
and Applied Mathematics 244, 67–76 (2013)
[14] An, P.T., Hoai, T.V.: Incremental convex hull as an orientation to solving
the shortest path problem. In: Proceeding of IEEE 3rd International
Conference on Computer and Automation Engineering, pp. 21–23 (2011)
[15] An, P.T., Huyen, P.T.T., Le, N.T.: A modified graham’s scan algorithm
for finding the connected orthogonal convex hull of a finite planar point
set. Applied Mathematics and Computation 397 (2021)
[16] Bajaj, C.: The algebraic complexity of shortest paths in polyhedral
spaces. In: Proceedings 23rd Annual Allerton Conference on Communi-
cation, Control and Computing, Monticello, Illinois, pp. 510–517 (1985)
[17] Balasubramanian, M., Polimeni, J.R., Schwartz, E.L.: Exact geodesics
and shortest paths on polyhedral surfaces. IEEE Transactions on Pattern
Analysis and Machine Intelligence 31(6), 1006–1016 (2009)
[18] Biedl, T., Genc, B.: Reconstructing orthogonal polyhedra from putative
vertex sets. Computational Geometry 44, 409–417 (2011)
[19] Bose, P., Maheshwari, A., Shu, C., Wuhrer, S.: A survey of geodesic
paths on 3d surfaces. Computational Geometry 44(9), 486–498 (2011)
[20] Breen, M.: A krasnosel’skii theorem for staircase paths in orthogonal
polygons. Journal of Geometry 51, 22–30 (1994)
[21] Canny, J., Reif, J.: Lower bounds for shortest path and related problems.
In: Proceedings 28th Annual Symposium on Foundations of Computer
Science, pp. 49–60. IEEE (1987)
74
[22] Chen, J., Han, Y.: Shortest paths on a polyhedron; part i: Computing
shortest paths. International Journal of Computational Geometry &
Applications 6, 127–144 (1996)
[23] Cheng, S., Jin, J.: Shortest paths on polyhedarl surfaces and terrains. In:
STOC ’14 Proceedings of the 64th Annual ACM Symposium on Theory
of Computing, pp. 373–382. IEEE (2014)
[24] Cheng, S.W., Jin, J.: Approximate shortest descending paths. In: Pro-
ceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algo-
rithms, pp. 144–155. SIAM (2013)
[25] Coddington, E.A., Levinson, N.: Theory of Ordinary Differential Equa-
tions. Tata McGraw-Hill (1955)
[26] Cook, I.A.F., Wenk, C.: Shortest path problems on a polyhedral surface.
Algorithmica 69(1), 58–77 (2014)
[27] Dror, M., Efrat, A., Lubiw, A.: Touring a sequence of polygons. In: Pro-
ceedings of the 35th Annual ACM Symposium on Theory of Computing,
pp. 473–482. IEEE (2003)
[28] Gonza´lez-Aguilar, H., Ordenand, D., Pe´rez-Lantero, P., Rappaport, D.,
Seara, C., Tejel, J., Urrutia, J.: Maximum rectilinear convex subsets. In:
Fundamentals of Computation Theory, 22nd International Symposium,
pp. 274–291. Springer (2019)
[29] Graham, R.: An efficient algorith for determining the convex hull of a
finite planar set. Information Processing Letters 1, 132–133 (1972)
[30] Gru¨nbaum, B.: Convex Polytopes. Springer (2003)
[31] Hai, N.N., An, P.T.: A generalization of blaschke’s convergence theorem
in metric spaces. Journal of Convex Analysis 4, 1013–1024 (2013)
[32] Hai, N.N., An, P.T., Huyen, P.T.T.: Shortest paths along a sequence
of line segments in euclidean spaces. Journal of Convex Analysis 26(4),
1089–1112 (2019)
[33] Hearn, D.D., Baker, P., Warren Carithers, W.: Computer Graphics with
Open GL. Person (2014)
[34] Hoai, T.V., An, P.T., Hai, N.N.: Multiple shooting approach for com-
puting approximately shortest paths on convex polytopes. Journal of
Computational and Applied Mathematics 317, 235–246 (2017)
75
[35] Karlsson, R.G., Overmars, M.H.: Scanline algorithms on a grid. BIT
Numerical Mathematics 28, 227–241 (1988)
[36] Lang, S., Murrow, G.: Geometry: A High School Course. Springer
Sciene+Business Media, LLC (1988)
[37] Li, F., Klette, R.: Euclidean Shortest Paths: Exact and Approximate
Algorithms. Springer (2011)
[38] Mitchell, J., Papadimitriou, C.: The weighted region problem: finding
shortest paths through a weighted planar subdivision. Journal of the
ACM 38, 18–73 (1991)
[39] Mitchell, J.S.: Geometric shortest paths and network optimization. In:
Handbook of Computational Geometry, pp. 633–701. Elsevier Science
Publishers B.V. North-Holland (2000)
[40] Mitchell, J.S.B.: Approximation schemes for geometric network opti-
mization problems. In: Encyclopedia of Algorithms, pp. 126–130 (2015)
[41] Mitchell, J.S.B., Mount, D.M., Papadimitriou, C.H.: The discrete
geodesic problem. SIAM Journal on Computing 16, 633–701 (1987)
[42] Montuno, D.Y., Fournier, A.: Finding the x-y convex hull of a set of x-y
polygons. Tech. Rep. 148, University of Toronto (1982)
[43] Nicholl, T.M., Lee, D.T., Liao, Y.Z., Wong, C.K.: On the x− y convex
hull of a set of x − y polygons. BIT Numerical Mathematics 23(4),
456–471 (1983)
[44] O’Rourke, J.: Computational Geometry in C. Cambridge University
Press (1998)
[45] O’Rourke, J., Suri, S., Booth, H.: Shortest paths on polyhedral surfaces.
Tech. Rep. Manuscript, The Johns Hopkins University, Baltimore (1984)
[46] Ottmann, T., Soisalon-Soininen, E., Wood, D.: On the definition and
computation of rectilinear convex hulls. Information Sciences 33(3), 157–
171 (1984)
[47] Papadopoulos, A.: Metric Spaces, Convexity and Nonpositive Curvature.
2ed., European Mathematical Society (2014)
76
[48] Pham-Trong, V., Szafran, N., Biard, L.: Pseudo-geodesics on three-
dimensional surfaces and pseudo-geodesic meshes. Numerical Algorithms
26, 305–315 (2001)
[49] Polthier, K., Schmies, M.: Straightest geodesics on polyhedral surfaces.
In: Mathematical Visualization, pp. 135–150. Springer (1998)
[50] Seo, J., Chae, S., Shim, J., Kim, D., Cheong, C., Han, T.D.: Fast
contour-tracing algorithm based on a pixel-following method for image
sensors. Sensors 16, 353 (2016)
[51] Sethian, J.A.: Fast marching methods. SIAM Review 41, 199–235 (1999)
[52] Shamos, M.I.: Computational Geometry. Ph.D. Dissertation, Depart-
ment of Computer Science, Yale University (1977)
[53] Sharir, M., Schorr, A.: On shortest paths in polyhedral spaces. SIAM
Journal on Computing 15(1), 193–215 (1986)
[54] Son, W., Hwang, S.W., Ahn, H.K.: Mssq: Manhattan spatial skyline
queries. Information Systems 40, 67–83 (2014)
[55] Steiner, J.: Gesammelte werke. Band 2, 45 (1882)
[56] Tran, N., Dinneen, M.J., Linz, S.: Computing close to optimal weighted
shortest paths in practice. In: Proceedings of the Thirtieth Interna-
tional Conference on Automated Planning and Scheduling (ICAPS), p.
291–299. AAAI Press (2020)
[57] Uchoa, E., de Aragao, M.P., Ribeiro, C.C.: Preprocessing steiner prob-
lems from vlsi layout. Networks 40, 38–50 (2002)
[58] Unger, S.H.: Pattern detection and recognition. In: Proceedings of the
Institute of Radio Engineers, pp. 1737–1752. IEEE (1959)
[59] Varadarajan, K., Agarwal, P.: Approximating shortest paths on a non-
convex polyhedron. SIAM Journal on Computing 30, 1321–1340 (2001)
[60] Xin, S.Q., Wang, G.J.: Efficiently determining a locally exact shortest
path on polyhedral surfaces. Computer-Aided Design 39(12), 1081–1090
(2007)
77