Algorithmic Studies in Applied Geometry

应用几何中的算法研究

• 批准号: 0431030
• 负责人: Joseph S. Mitchell
• 金额: $ 25.5万
• 依托单位: SUNY at Stony Brook
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2004
• 资助国家: 美国
• 起止时间: 2004-09-01 至 2008-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0431030&HistoricalAwards=false
• 关键词: Algorithmic; Studies; Applied; Geometry

There is a driving need to process geometric data efficiently in many applications, including manufacturing, computer-aided design, graphics and visualization, robotics, air traffic management, and cartography. This project applies the methodologies of computational geometry to design, analyze, implement, and test efficient algorithms for such problems. In addition to development of fundamental advances in geometric algorithms, an important goal is dissemination of implemented algorithms to application domains, while assisting practitioners in formulating precise instances of their problems for algorithmic investigation. The intellectual merit of the project lies in the development of novel algorithmic solutions for several fundamental problems in geometry. Many of the problems are posed in terms of optimization criteria; solutions to these problems are given in the form of algorithms for exact optimization, approximation algorithms, and experimental comparisons. New algorithmic techniques and extensions to existing methods are developed, while newly formulated algorithmic questions arising in application domains are precisely posed for study by the community of algorithmic engineers. The project has broader impact in the targeted application areas, including manufacturing, virtual environments, homeland security, robotics, geographic information systems, military logistics, and air traffic management. The project incorporates a tightly-integrated educational mission, through courses, seminars, and training of both graduate and undergraduate students. The specific focus areas include geometric optimization and networks (optimal network design, optimal constrained route planning, facility location, terrain simplification, map generalization in GIS, clustering); virtual prototyping, manufacturing, and computer-aided design (milling/process planning, virtual prototyping and maintenance, generative design tools, geometric modeling, high-speed rendering methods, visibility computation, surface parameterization and texture mapping); sensor networks and swarm robotics (sensor deployment, robotic dispersion, geometric map extraction, ad hoc networking for stationary or mobile sensors); and air traffic management (conflict prediction and resolution, congestion and uncertainty modeling, routing of aircraft flows in the presence of dynamic and uncertain weather conditions, and optimal redesign of the National Airspace System).

在许多应用程序中有效地处理几何数据，包括制造，计算机辅助设计，图形和可视化，机器人技术，空中交通管理和制图。该项目将计算几何形状的方法论用于设计，分析，实施和测试此类问题的有效算法。除了发展几何算法的基本进步外，一个重要的目标是将实施算法传播到应用领域，同时协助从业者制定其问题的精确实例进行算法调查。该项目的智力优点在于开发新的算法解决方案，用于几何学的几种基本问题。许多问题是根据优化标准提出的。这些问题的解决方案以算法的形式给出，以进行精确优化，近似算法和实验比较。 开发了新的算法技术和对现有方法的扩展，而在应用领域中出现的新提出的算法问题是由算法工程师社区精确提出的。该项目在针对性的应用领域具有更大的影响，包括制造，虚拟环境，国土安全，机器人技术，地理信息系统，军事物流和空中交通管理。 该项目通过课程，研讨会和研究生和本科生的课程，研讨会和培训结合了一个紧密融合的教育任务。特定的重点领域包括几何优化和网络（最佳网络设计，最佳约束路线计划，设施位置，地形简化，GIS中的地图概括，聚类）；虚拟原型制造，制造和计算机辅助设计（铣削/过程计划，虚拟原型和维护，生成设计工具，几何建模，高速渲染方法，可见性计算，表面参数化和纹理化映射和纹理映射）；传感器网络和群机器人（传感器部署，机器人分散，几何图提取，用于固定或移动传感器的临时网络）；和空中交通管理（冲突预测和解决，拥堵和不确定性建模，在有动态和不确定天气条件的情况下飞机流动的路线以及国家空域系统的最佳重新设计）。