Algorithmic Studies in Applied Geometry

在许多应用中，包括制造、计算机辅助设计、图形和可视化、机器人、空中交通管理和制图，都迫切需要高效地处理几何数据。这个项目应用计算几何的方法来设计，分析，实现和测试这些问题的有效算法。除了几何算法的基本进展的发展，一个重要的目标是传播实现算法的应用领域，同时协助从业者在制定精确的算法调查的问题。该项目的智力价值在于为几何学中的几个基本问题开发新的算法解决方案。许多问题提出的优化标准，这些问题的解决方案给出的形式的算法，精确优化，近似算法，和实验比较。 新的算法技术和现有方法的扩展被开发出来，而新制定的算法问题在应用领域中出现的正是算法工程师社区的研究。该项目在目标应用领域具有更广泛的影响，包括制造业、虚拟环境、国土安全、机器人技术、地理信息系统、军事物流和空中交通管理。 该项目通过课程、研讨会和对研究生和本科生的培训，纳入了一个紧密结合的教育使命。具体的重点领域包括几何优化和网络（最佳网络设计、最佳约束路线规划、设施选址、地形简化、GIS中的地图综合、聚类）;虚拟样机、制造和计算机辅助设计（铣削/工艺规划、虚拟原型和维护、生成式设计工具、几何建模、高速渲染方法、可视性计算，表面参数化和纹理映射）;传感器网络和群机器人（传感器部署、机器人分散、几何地图提取、固定或移动的传感器的自组织联网）;和空中交通管理（冲突预测和解决，拥塞和不确定性建模，在动态和不确定的天气条件下的飞机流路由，以及国家空域系统的最佳重新设计）。

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