Algorithmic Studies in Applied Geometry

应用几何中的算法研究

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

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.

计算几何形状的方法将用于设计，分析，实施和测试算法，以了解在几个应用领域中出现的问题，包括几何网络优化，传感器网络，机器人技术，空中交通管理，几何几何建模，制造，计算机辅助，计算机辅助，定位，制图和图形。主要项目目标是发展几何算法的基本进步。 此外，该项目将努力促进和加深与应用领域和行业研究人员的合作，以精确地制定其算法需求，并提供算法工具，理论结果的见解以及实验研究的软件。四个问题领域是：（a）。几何优化和网络 - 几何环境中的最佳路由和网络设计，包括TSP变体，车辆路由，约束跨越树木，最小重量分区，具有各种约束的最佳路线计划以及可生存的网络设计； （b）。传感器网络和群体机器人技术 - 传感器定位，传感器覆盖范围和部署，数据现场监视以及用于固定或移动（机器人）传感器的临时网络； （c）。空中交通管理 - 面对天气和交通拥堵，部门化（负载平衡）以及国家空域系统网络结构的优化，面对动态和不确定的限制，空域的最佳使用； （d）。形状近似，虚拟模型和制造 - 形状近似，碰撞检测，虚拟原型和制造过程计划。问题在两个方面受到攻击：（1）正式算法分析的应用，试图证明在最差的或平均时间/平均空间或平均空间或平均空间或近似值的问题上，试图证明最紧密的界限（上和下部），或（2）旨在简单，快速和实用的解决方案技术的开发，可以通过实验进行比较。