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, air traffic management, sensor networks, robotics, geometric modeling, and manufacturing. The main project goal is the development of fundamental advances in approximation algorithms for geometric problems. Additionally, the project will strive to foster and deepen collaborations with researchers and domain experts in application areas 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 specific repertoire of problems includes: (a) Geometric Network Optimization: optimal routing and network design in geometric contexts, including traveling salesman (TSP) variants, vehicle routing, constrained spanning trees, minimum-weight subdivisions, optimal route planning with various constraints, and survivable network design; (b) 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 flow management structures for the National Airspace System; (c) Sensor Networks and Coverage: sensor deployment, localization, data field monitoring, and coverage for stationary or mobile (robotic) sensors.
The problems will be attacked on two fronts: (1) Use 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, and which are compared experimentally.
This project's aim was to devise new, efficient algorithms for a variety of optimization problems in geometric domains. The problems studied arise in transportation engineering, facility location, wireless networks, and robotics. Consider, for example, the problem of determining a shortest route for a mobile robot within a building in order that its cameras can scan and see all parts of the building. This visibility coverage tour problem is a generalization of the well studied "Traveling Salesman Problem" (TSP)-- find an optimal order in which to visit a set of cities, in order to minimize the total distance traveled -- which is known to be provably hard to solve. Computing an optimal visibility coverage tour for a robot is "even harder" than the TSP, so the goal is to devise efficient algorithms that yield nearly optimal tours, in a provable sense, in much the same way that prior efforts have led to very effective approximations for geometric TSP instances. No prior methods were known for visibility coverage tours with any guarantees about their relationship in comparison with an optimal solution. The project devised several such approximation algorithms for geometric optimization problems that involve "coverage" and routing. For instance, another classic optimization problem is the "art gallery problem", in which we are to place the fewest cameras within a known environment (floorplan), in order that all of the environment is seen. This project worked towards new solutions for this and related coverage problems. The new algorithms rely on structural results about how optimal solutions and nearly optimal solutions behave. The project also examined optimal location problems that arise in placement of recharging stations for electric vehicles, optimal structure of air traffic lanes for safe weather avoidance, and optimal message passing in wireless networks. All of these application-motivated geometric optimization problems require tools from analysis of algorithms,geometric approximation methods, and combinatorial optimization. This project helped advance the state of the art in these techniques while expanding the set of applications for which effective solutions and algorithms are known.
