Algorithmic Studies in Applied Geometry

计算几何方法论将被应用于设计、分析、实现和测试在几个应用领域出现的问题的算法，包括几何网络优化、传感器网络、机器人、空中交通管理、几何建模、制造、计算机辅助设计、制图和图形学。该项目的主要目标是发展几何算法的基本进展。此外，该项目将努力促进和深化与应用领域和行业的研究人员的合作，以便准确地制定他们的算法需求，并提供算法工具、来自理论结果的见解和来自实验研究的软件。几何优化和网络--几何环境下的最优路径和网络设计，包括TSP变量、车辆路径、约束生成树、最小重量细分、各种约束的最优路径规划和可生存网络设计；(B)传感器网络和群体机器人--传感器定位、传感器覆盖和部署、数据现场监测以及固定或移动(机器人)传感器的特别联网；(C)空中交通管理--面对天气和交通拥堵造成的动态和不确定的限制，优化利用空域，分区(负载平衡)，优化国家空域系统的网络结构；(D)形状近似、虚拟模型和制造--形状近似、碰撞检测、虚拟样机和制造过程计划。这些问题从两个方面展开：(1)形式化算法分析的应用，试图证明问题在最坏情况或平均情况下的时间/空间或近似比的最小可能界；(2)开发简单、快速和实用的解决方法，并通过实验进行比较。

The methodologies of computational geometry will be applied to design, analyze, implement, and test algorithms for problems that arise in several application areas, including geometric network optimization, sensor networks, robotics, air traffic management, geometric modeling, manufacturing, computer-aided design, cartography, and graphics. The main project goal is the development of fundamental advances in geometric algorithms. Additionally, the project will strive to foster and deepen collaborations with researchers in application domains and industry, in order to formulate their algorithmic needs precisely and to make available algorithmic tools, insights from theoretical results, and software from experimental investigations.The four problem areas are: (a). Geometric Optimization and Networks -- optimal routing and network design in geometric contexts, including TSP variants, vehicle routing, constrained spanning trees, minimum-weight subdivisions, optimal route planning with various constraints, and survivable network design; (b). Sensor Networks and Swarm Robotics -- sensor localization, sensor coverage and deployment, data field monitoring, and ad hoc networking for stationary or mobile (robotic) sensors; (c). Air Traffic Management -- optimal use of airspace in the face of dynamic and uncertain constraints induced by weather and traffic congestion, sectorization (load balancing), and optimization of the network structure of the National Airspace System; (d). Shape Approximation, Virtual Models, and Manufacturing -- shape approximation, collision detection, virtual prototyping, and manufacturing process planning.The problems are attacked on two fronts: (1) Application of formal algorithmic analysis, attempting to prove the tightest possible bounds (upper and lower) on the worst-case or average-case time/space, or approximation ratio for the problem; and (2) Development of solution techniques designed to be simple, fast, and practical, which are compared experimentally.