Design and analysis of algorithms for problems in computational geometry

点击翻译按钮获取中文摘要

I study computational problems within the framework of the design and analysis of algorithms. The solution to a problem requires designing an efficient algorithm and supporting data structures, analyzing their complexities, and providing correctness proofs. My long term research objectives are to design, analyze and implement algorithms for problems that require spatial information and (a) are fundamental, (b) have practical significance, (c) are theoretically-challenging and have the potential to raise new questions, (d) contribute to an understanding of a methodology or concept, (e) lead to the development of generic techniques and tools that apply to other problems, and (f) are of interest to students, members of our research lab, and to many of my collaborators worldwide. To have a flavour of my research, let us consider the following abstract algorithmic problem inspired by mobile networks. Consider a set of points (mobile nodes) where each point moves along a vector, and we want to maintain a fixed connection network between them. During the entire motion of points, the links (i.e., the range) connecting the points may shrink or expand, but the connections remain fixed. Two natural optimization problem arise: Minimum Moving Spanning Tree Problem:  Find a fixed connection network between moving points that minimizes the total length of the links required at any point in time during the entire motion. We show that this problem is intractable and provide an efficient algorithm for computing a spanning tree whose length is within a factor of 2 of an optimal tree. Minimum Moving Bottleneck Tree Problem: Find a fixed connection network between moving points that minimizes the longest link length. We provide an efficient algorithm for computing an optimal tree. In network architectures containing mobile nodes, the existing methods that maintain a connected network update the topology dynamically. Such networks' stability becomes an essential factor since costs are associated with establishing new connections and handing over ongoing sessions. Our approach of maintaining spanning trees of good quality ensures that we have a fixed connection network even when the nodes are moving. It altogether avoids the need for reconfiguration and provides stability.  In the short term, my research focus primarily will be on algorithmic and combinatorial problems arising in geometric spanning trees, matchings, and paths. We will outline several exciting and important research problems. The common theme in addressing these problems is understanding the geometric and combinatorial structure of the input spatial configuration and exploiting them to design efficient data structures and algorithms. We expect that the Undergraduate, Masters, Doctoral, and Postdoctoral students with appropriate maturity level, effort, and guidance can solve them. The research training will prepare them to tackle challenging computational problems of the 21st century.