Geometric Computing

我的研究领域是计算几何，这是一个致力于设计和分析几何问题的算法和数据结构的领域。我的研究侧重于理论和实践问题。我主要研究的几何应用领域包括网络中的在线路由和路径规划，各种属性的几何扳手的构建，图形的绘制和可视化，以及各种几何结构的优化。一个算法在理论上被证明是有效的，但在实际中往往是无用的，因为只有当问题的规模过大或算法太复杂而无法实现时，它才会变得有效。然而，理论上有效的算法的存在往往提供对问题的见解，并导致在实践中同样有效的算法的发展。我研究的主要目标一直是并将继续是通过寻找具有理论性能保证的应用几何问题的实用算法解决方案来弥合理论和实际效率之间的差距。下面，我提供一个例子，说明我目前关注的几何问题类型。建议中提供了更详细和完整的描述。通信网络通常具有固有的几何成分，因为通信设备具有物理位置。这些网络通常用几何图形来建模。几何图形是这样一种图形，其中每个顶点是平面上的一个点（或者可能是更高的维度，取决于应用程序），而边是连接两点的线段或曲线。边缘通常被加权以表示两点之间的距离（或通信成本等）。这个领域的一个基本问题是找到图中两点之间的路径（通常尽可能短）。目前，我正在运用我在几何方面的专业知识开发算法，利用这些图的几何成分以有效的方式找到短路径。这方面的问题尤其具有挑战性，因为网络通常是动态的，即设备可能会移动，边缘可能会出现或消失。此外，这种动态特性意味着没有一个实体完全了解整个网络的当前状态，这就要求开发在线的、本地的、占用很少内存的算法。这相当于试图在图发生变化时在图中找到一条路径。我在这一领域的研究主要集中在以下主题：(1)如何在不同设置的几何网络中有效地路由（即找到路径），(2)如何构建具有某些理想属性的几何网络？在解决几何问题时，我研究的一个统一主题是首先揭示问题中涉及的结构的各种几何属性，然后尝试利用这些属性来设计有效的数据结构和算法来解决几何问题。

My research area is Computational Geometry, a field devoted to the design and analysis of algorithms and data structures for geometric problems. My research focuses both on theoretical and practical issues. The geometric application areas I concentrate on include online routing and path planning in networks, building geometric spanners with various properties, drawing and visualizing graphs, and optimizing various geometric structures. An algorithm that is proven to be theoretically efficient often fails to be practically useful as it may only become efficient when the size of the problem is unreasonably large or the algorithm may be too complex to implement. However, the existence of theoretically efficient algorithms often provides insights into a problem and leads to the development of algorithms that are equally efficient in practice. The main goal of my research has been and continues to be to bridge the gap between theoretical and practical efficiency by finding practical algorithmic solutions to applied geometric problems that have theoretical performance guarantees. Below, I provide an example of the type of geometric problems I am currently concentrating on. More detailed and complete descriptions are provided in the proposal. Communication networks often have an inherent geometric component since the communication devices have physical locations. These networks are often modeled by geometric graphs. A geometric graph is a graph where each vertex is a point in the plane (or possibly higher dimensions depending on the application) and an edge is a line segment or a curve joining two points. The edges are often weighted to represent the distance between two points (or the communication cost etc.). A fundamental problem in this area is to find a path (usually as short as possible) between two points in the graph. Currently, I am applying my expertise in geometry to develop algorithms that take advantage of the geometric component of these graphs to find short paths in an efficient manner. The problems in this area are particularly challenging since the network is often dynamic, i.e. the devices may be moving and edges may appear or disappear. Moreover, this dynamic nature means that no single entity has complete knowledge of the current state of the whole network, requiring the development of algorithms that are online, local and use little memory. This amounts to trying to find a path in a graph while the graph is changing. My research in this area focuses on the following themes: (1) How to route (i.e. find a path) efficiently in a geometric network in various settings, (2) how to construct geometric networks with certain desirable properties? A unifying theme in my research when solving a geometric problem has been to first uncover various geometric properties of the structures involved in the problem, then to attempt to exploit these properties to design efficient data structures and algorithms to solve the geometric problem.