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