RIA: Sparse Geometric Spanners, Geometric Analysis, and Applications

RIA：稀疏几何扳手、几何分析和应用

• 批准号: 9409752
• 负责人: Giri Narasimhan
• 金额: $ 6万
• 依托单位: University of Memphis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-07-15 至 1998-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9409752&HistoricalAwards=false
• 关键词: RIA; Sparse; Geometric; Spanners; Analysis

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. ***

9409752 Narasimhan本研究解决稀疏几何扳手问题及其许多变体。 给定一个图G和t1，一个t-图是G的一个边子图G'，使得G'中每对顶点之间的距离都在G中每对顶点之间的距离的一个因子t之内。 几何图的顶点对应于欧几里德空间中的点，它们的边权重对应于欧几里德距离。 许多实际应用需要稀疏的几何空间。 稀疏性是根据大小（边缘的数量）和/或权重（边缘的权重之和）来测量的。 将研究问题的各个方面：如何构造稀疏空间（算法）？ 如何分析输出的质量（几何分析）？ 问题的复杂性（复杂性和可近似性）是什么？ 如何设计有效的算法（实际实现）？ 此外，亦会研究问题的变种，包括连接性限制的空间和单源空间。 这在分析许多实际的几何算法的性能和研究最佳几何结构，如最小斯坦纳树，最佳spiritual和最佳三角剖分的应用。 ***