RIA: Sparse Geometric Spanners, Geometric Analysis, and Applications

9409752 Narasimhan这项研究解决了稀疏几何扳手问题及其许多变体。给定图G和t1， t-扳手是G的边子图G‘，使得G’中每对顶点之间的距离在G中距离的t因子内。几何图的顶点对应于欧几里得空间中的点，其边权对应于欧几里得距离。许多实际应用需要稀疏几何扳手。稀疏性是根据大小（边的数量）和/或权重（边的权重之和）来衡量的。该问题的各个方面将被研究：如何构建稀疏生成器（算法）？如何分析产品质量（几何分析）？问题的复杂性是多少（复杂性和近似性）？如何设计高效的算法（实际实现）？还将研究该问题的变体，包括连接受限扳手和单源扳手。这在分析许多实际几何算法的性能和研究最优几何结构，如最小斯坦纳树、最优扳手和最优三角剖分中都有应用。* * *

9409752 Narasimhan This investigation addresses the Sparse Geometric Spanner problem and its many variants. Given a graph G and t1, a t-spanner is an edge subgraph G' of G such that the distances between every pair of vertices in G' are within a factor of t of their distances in G. Geometric graphs have vertices corresponding to points in the Euclidean space and their edge weights correspond to Euclidean distances. Many practical applications require sparse geometric spanners. Sparseness is measured in terms of size (number of edges), and/or weight (sum of weights of edges). Various aspects of the problem will be studied: How to construct sparse spanners (algorithms)? How to analyze quality of the output (geometric analysis)? What is the complexity of the problem (complexity and approximability)? How to design efficient algorithms (practical implementations)? The study of variants of the problem including connectivity-constrained spanners and single-source spanners will also be undertaken. This has applications in analyzing the performance of many practical geometric algorithms and studying optimal geometric structures like minimum steiner trees, optimal spanners, and optimal triangulations. ***