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 - 2022
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 - 2022
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.
January 10, 2022
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 members of the Thesis Evaluation Committee at
the Department-Level and the Thesis Evaluation Committee at the Institute-
Level (Professor Nguyen Dong Yen, Professor Le Dung Muu, Associate Pro-
fessor Truong Xuan Duc Ha, Associate Professor Nguyen Nang Tam, Asso-
ciate Professor Nguyen Trung Thanh, Associate Professor Nguyen Thi Thu
Thuy, Doctor Hoang Nam Dung, Doctor Nguyen Duc Manh, Doctor Le Xuan
Thanh 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 ix
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 StraightestPaths ......................... 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