Algorithmic Studies in 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).