Information Technology has enabled new levels of convenience to our daily life. While providing people with astonishingly good experiences, computer science has still a long way to meet the needs from the users for various scenarios. As a good example, path selection problem is an important and common problem which finds applications in location based services, internet routing and navigation systems. Choosing the most cost effective and time saving routines plays an essential role in both theory and engineering. Although a plethora of classical solutions have been made to the static shortest path problem, dynamic shortest path problem has not been thoroughly studied. To address this critical issue, this paper investigates the dynamic shortest path problem by optimizing existing work and conducting extensive experiments. The studies fall into three main variants of the problem: unweighted shortest paths, weighted shortest paths, and shortest paths on the map. We present a comprehensive comparison of our optimizations and existing solutions which demonstrates the effectiveness and efficiency of our algorithms.

Polyhedral combinatorics has been a topic of interest in modern day’s computational geometry. The founding of Steinitz’s Theorem in 1922 revealed consequential relations between graph theory and polyhedral combinatorics. It allows us to better investigate on the topology of convex polyhedrons. In this paper, we proposed an algorithm that generates a unique sequence of points, using the vertices of a triangulated polyhedron, pre-determined by the selection of the starting 3 vertices in the sequence. Following that, we discover an interesting relation between the sequence and the volume of the polyhedron itself, in which we presented in the form of a sufficient condition. To further investigate which polyhedrons generate sequences that satisfy the sufficient condition, we study the problem in the context of graph theory, that is, the explorer walk (corresponding to the sequence of vertices) in maximal planar graphs (skeletons of triangulated convex polyhedrons). With that, we uncovered a family of maximal planar graphs, called the explorer graphs, which exhibits volumetric properties in the polyhedrons constructed from them, in regard to the explorer walk. In this paper, we also introduce generalized methods of constructing explorer graphs of higher order from explorer graphs of lower order, demonstrating the prevalence of explorer graphs. As the edges of a maximal planar graph is of great importance in tracing an explorer walk, we investigate on the line graph of maximal planar graphs, and re-establish a better definition of explorer graphs. Lastly, our paper covers the edge contraction of explorer graphs, which allows us to solve the volume of polyhedrons constructed from non-explorer graphs. For this, we presented a possible bound for the minimum number of edge contractions a non-explorer graph requires from an explorer graph. This will generalize the proposed method of finding volumes to any triangulated convex polyhedron.

No abstract uploaded!

We proved in this paper that 14 triangles are necessary to triangulate a square with every angle no more than 72◦, answering an unsolved problem proposed by Professor D.Eppstein. At first, computer is used to search for topologically feasible solutions of triangulations of a rectangle. Then the geometric feasibility is analyzed case by case by plane geometry. We also proved that any rectangle can be 72◦ triangulated if the number of triangles is not limited.

No abstract uploaded!