Efficient geometric algorithms and applications
In this dissertation, we study a set of challenging geometric computing and optimization problems arising in Medical Imaging, Treatment Planning, and VLSI Design. We present the efficient algorithms to solve the following four problems. First, we consider the problem of computing a map of geometric minimal cuts (called MGMC problem): Given a graph G =( V,E ) and a planar rectilinear embedding of a subgraph H =( V H , E H ) of G, compute the map of geometric minimal cuts induced by axis-aligned rectangles in the embedding plane. The MGMC problem is motivated by the critical area extraction problem in VLSI designs and finds applications in several other fields. To solve this problem, we present a novel approach based on a mix of geometric and graph algorithm techniques for the MGMC problem. Our approach first shows that unlike the classic min-cut problem on graphs, the number of all rectilinear geometric minimal cuts is bounded by a low polynomial, O ( n 3 ). Our algorithm for identifying geometric minimum cuts runs in O ( n 3 log n (log log n ) 3 ) time in the worst case which can be reduced to O ( n log n (log log n ) 3 ) when the maximum size of the cut is bounded by a constant, where n =| V H |. Once geometric minimal cuts are identified we show that the problem can be reduced to computing the L ∞ Hausdorff Voronoi diagram of axis aligned rectangles. We present the first output-sensitive algorithm to compute this diagram which runs in O (( N + K ) log 2 N log log N ) time and O ( N log 2 N ) space, where N is the number of rectangles and K is the complexity of the Hausdorff Voronoi diagram. Our approach settles several open problems regarding the MGMC problem. Second, we study the problem of computing a minimum bending energy path (or MinBEP) in a simple corridor. The MinBEP problem considered in this dissertation is motivated by applications in intervational procedures for cardiovascular surgery. Given a simple 2D corridor C bounded by straight line segments and arcs of radius 2 r, the MinBEP problem is to compute a path P inside C and crossing two pre-specified points s and t located at each end of C so that the bending energy of P is minimized. For this problem, we first show how to lower bound the bending energy of an optimal curve with bounded curvature, and then use this lower bound to design a (1 + ε)-approximation algorithm for this restricted version of the MinBEP problem. Our algorithm is based on a number of interesting geometric observations and approximation techniques on smooth curves, and can be easily implemented for practical purpose. It is the first algorithm with a guaranteed performance ratio for the MinBEP problem. Third, we present a novel and efficient method to simulate the behavior of guidewires in the vascular system. The graph-theoretical method is based on the principle of minimal total potential energy. We formulate the total potential energy in the vascular interventional system as the summation of the elastic energy of the guidewire and the energy due to the deformation of the vessel wall. A graph is constructed with low complexity ensuring the efficiency of the single source shortest path. Compared to previous results, experiments in three phantoms have been conducted to evaluate the performance of the proposed method and the results demonstrate that our method can achieve 20% improvement with faster running time. Finally, despite extensive studies in the past, the problem of segmenting globally optimal single and multiple surfaces in 3D volumetric images remains challenging in medical imaging. The problem becomes even harder in highly noisy and edge-weak images. We present a novel and highly efficient graph-theoretical iterative method with bi-criteria of global optimality and smoothness for both single and multiple surfaces. Our approach is based on a volumetric graph representation of the 3D image that incorporates curvature information. To evaluate the convergence and performance of our method, we test it on a set of 14 3D OCT images. Our experiments suggest that the proposed method yields optimal (or almost optimal) solutions in 3 to 5 iterations. To the best of our knowledge, this is the first algorithm that utilizes curvature in objective function to ensure the smoothness of the generated surfaces while striving for achieving global optimality. Comparing to the best existing approaches, our method has a much improved running time, yields almost the same global optimality but with much better smoothness, which makes it especially suitable for segmenting highly noisy images.