From The Discrete Geodesic Problem To The Dynamic Ordered Set Problem

The discrete geodesic problem is to determine the shortest path between two points restricted on a polyhedral surface.It arises naturally in applications such as terrain navigation and motion planning,and becomes an important textbook problem in computational geometry.Seeking an algorithm of high performance for this problem is not only the important task of digital geometry processing, but also the inevitable requirement of the development of Computer Graphics.The discrete geodesic problem has three versions,"single source,single destination", "single source,any destination" and "any source,any destination", depending on the amount of source points and destination points.The "single source,any destination" version,the foundation of the other two problems,is particularly important.In 1986,Sharir and Schorr inherited the idea of Dijkstra's algorithm and gave an O(n~3 log n)-time algorithm that only applies to convex polytopes,where n is the face number.It is,nevertheless,the first polynomial algorithm on this problem.Later,Mitchell et al.(MMP) used a window to encode the information of a set of shortest paths passing through the same edge sequence and improved the problem to O(n~2 log n)-time and O(n~2)-space by fulfilling the idea of "continuous Dijkstra" to extremes.The MMP algorithm works for general polyhedral surfaces.In 1990,Chen and Han(CH) found that for each edge,at most one window is necessary to generate two children at the same time. So in a different way,they arranged the windows into a tree of an O(n~2) size and then proved that the discrete geodesic problem can be solved in O(n~2) time and O(n) space.Interestingly,Surazhsky et al.provided experimental evidence,in a SIGGRAPH '05 paper,demonstrating that the O(n~2 log n)-time MMP algorithm runs many times faster,in practice,than the O(n~2)-time CH algorithm.In order to reveal the reasons,we made a deep investigation into the discrete geodesic problem.We found that the CH algorithm,in spite of its low time complexity,builds a large tree containing a lot of useless windows.Our experiments showed that in many examples over 99%of the windows created by the CH algorithm don't contribute when determining a shortest path.Therefore we propose to improve the CH algorithm with two separate techniques.One,is to give a window filtering theorem to filter out useless windows using the current estimates of the distances to vertices,the other is to maintain a priority queue like that achieved in Dijkstra's algorithm so that the "nearest" event can be first handled.Numerous experimental results suggest that the improved CH algorithm(called "the XW algorithm" later) outperforms the original CH algorithm over a thousand times.Compared with the MMP algorithm,the XW algorithm generally runs faster and requires considerably less space.So we believe that the XW algorithm is the preferred choice for the "single source,any destination" problem.However,we must point out that maintaining a priority queue increases the theoretical asymptotic time complexity of the XW algorithm to O(n~2 log n).To do the further research,we focused on two topics:one is to seek more algorithms on the discrete geodesic problem,the other is to explain why the operation of maintaining a priority queue improves the performance in practice while increases the theoretical time complexity.We made four contributions on the first topic:(1) We classified all the edges into seven types according to Huygens' principle,improved the famous Fast Marching Method(FMM) to a better approximation algorithm for determining the "single source,any destination" problem.(2) We used the technique ofε-error control in the XW algorithm to overly filter out interval windows,obtaining an approximation algorithm with adjustable accuracy.Ifε=0,it is the same as the XW algorithm;and ifε→∞,it degenerates into Dijkstra's algorithm. (3) Inspired by Fermat's principle which affirms that light always follows the shortest optical path,we proposed a visibility-based algorithm to evolve an initial approximately shortest path into a locally exact shortest path with finite iterations.Furthermore,the resulting path is globally exact shortest if the initial path is accurate enough.(4) We induced an A~* algorithm,from the CH algorithm or the XW algorithm,to provide an exact solution for the "single source, single destination" problem.As to the second research topic,we analyzed carefully some classical algorithms using priority queues and found similar paradoxes.Taking Dijkstra's algorithm for example,if we propagate discrete events level by level rather than maintain a priority queue,its time complexity will reduce from O(m+n log n) to O(m) provided that the graph of interest is close to a tree-type structure or the weights of edges are very close to each other,where m,n are respectively the edge number and the vertex number of the graph.This contradicts our intuition that maintaining a priority queue is a generally adaptable technique.So we guess that maintaining a priority queue should be a constant-time operation without increasing the time complexity of the algorithm of interest.To prove the hypothesis,we investigated a broader problem,i.e.,how to maintain an efficient dynamic ordered set of bit strings that supports 5 essential operations including search,insertion,deletion,max-value retrieval and next-larger-value retrieval. For this purpose,we invented an advanced data structure named Rich Binary Tree(RBT) which follows both the binary-search-tree property and the digital-search -tree property.Also,every key K keeps the most significant difference bit (MSDB) between itself and the next larger value among K's ancestors,as well as that between itself and the next smaller one among its ancestors.We further gave a set of O(L)-time algorithms for maintaining RBT-based dynamic ordered sets, where L is the word length of input keys.So RBT supports O(L)-time search, O(nL)-time sorting and O(L)-time priority queues.With the assumption of L being a constant,we can conclude that maintaining a priority queue doesn't increase the time complexity at all.This accounts for the above paradoxes in a way.In fact,RBT is a general-purpose data structure and can serve as an effective tool for solving problems regards ordering,such as search,sorting and maintaining a priority queue.For example,when RBT is applied in sorting,we get a linear-time algorithm with regard to the key number and the performance is far better than the traditional O(n log n)-time quick-sort.What is more powerful than quick-sort is that RBT supports constant-time dynamic insertion/deletion.Because the XW algorithm outperforms the CH algorithm over a thousand times in running time and the MMP algorithm about a hundred times in space respectively,this fundamental revolution can hopefully result in a series of hot research in both theory and application on the discrete geodesic problem.In light of the important position of this problem,there is no doubt that the XW algo- rithm will contribute a lot to the development of Discrete Differential Geometry. Since the algorithm has advantages in both time and space,and the resulting shortest paths are globally exact,it will be widely applied in Digital Geometry Processing and Computer Graphics.For example,similarity-based surface modeling, parameterization of surfaces,cutting a mesh into serval charts,definition of distance metric over a space surface and remeshing can find an excellent solution using shortest paths.On the dynamic ordered set problem,we present a welldesigned RBT data structure with good properties,which appeared for the first time in Computer Science.The RBT structure,as well as the RBT-based algorithms, will greatly increase the ability and efficiency of information processing, and will positively push Algorithm Theory to approach perfection.Our research fruits have apparent values in both theory and application.