Design and analysis of algorithms for problems in computational geometry

我在算法设计和分析的框架内研究计算问题。一个问题的解决方案需要设计一个有效的算法和支持数据结构，分析它们的复杂性，并提供正确性证明。我的长期研究目标是为需要空间信息的问题设计、分析和实施算法，并且(a)是基本的，(b)具有实际意义，(c)具有理论挑战性并有可能提出新问题，(d)有助于理解方法或概念，(e)导致适用于其他问题的通用技术和工具的发展，以及(f)是学生，我们的研究实验室成员，也感谢我在世界各地的许多合作者。为了更好地理解我的研究，让我们考虑一下下面这个受移动网络启发的抽象算法问题。考虑一组点（移动节点），其中每个点沿着向量移动，我们希望在它们之间保持固定的连接网络。在点的整个运动过程中，连接点的链接（即范围）可能会缩小或扩大，但连接保持固定。两个自然优化问题出现了：最小移动生成树问题：在整个运动过程中，找到一个固定的运动点之间的连接网络，使整个运动过程中任何时间点所需的链路总长度最小。我们证明了这个问题是难以处理的，并提供了一种有效的算法来计算长度在最优树的2因子内的生成树。最小移动瓶颈树问题：寻找移动点之间的固定连接网络，使最长连接长度最小。我们提供了一种计算最优树的有效算法。在包含移动节点的网络体系结构中，现有的维护连接网络的方法动态地更新拓扑结构。这种网络的稳定性成为一个重要因素，因为建立新连接和移交正在进行的会话的成本是相关的。我们维护高质量生成树的方法确保了即使节点在移动，我们也有一个固定的连接网络。它完全避免了重新配置的需要，并提供了稳定性。在短期内，我的研究重点主要是几何生成树、匹配和路径中出现的算法和组合问题。我们将概述几个令人兴奋和重要的研究问题。解决这些问题的共同主题是理解输入空间配置的几何和组合结构，并利用它们来设计有效的数据结构和算法。我们希望本科生、硕士、博士和博士后在适当的成熟度、努力和指导下能够解决这些问题。研究训练将使他们为解决21世纪具有挑战性的计算问题做好准备。

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.