Algorithmic Studies in Applied Geometry

Proposal #0098172 Mitchell, Joseph S. B. SUNY Stony Brook 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 manufacturing, computer-aided design, graphics and visualization, robotics, air traffic management, and cartography. An important aspect of the project is dissemination of the technology to industry, helping to transfer algorithms into practice, while, at the same time, extracting from practitioners a set of high-priority problem areas for further investigation. New industrial collaborations will be pursued, while building on the several industrial partnerships that have already been established. In visitations with practitioners, new applications and mathematical formulations of geometric problems will be developed, and critical algorithmic issues in geometric computation will be identified. Further, as solutions are proposed and developed, the industrial partners will be assisted with the implementation and integration phases of the projects. The specific repertoire of problems includes: (a) manufacturing process planning (tool path generation, NC verification, bending and folding, deposition, cutting) and virtual manufacturing and maintenance (collision detection, assembly planning); (b) computer graphics and visualization (rendering large polygonal models, data compression, irregular grid volume visualization, visibility preprocessing, optimized texture mapping); (c) Air Traffic Management (conflict detection and resolution, congestion modeling); (d) Mobile robotics (multiple robot search and exploration); (e) Geographic Information Systems (GIS), including map generalization, optimal route planning in geometric environments under a variety of constraints and objectives, and network design and optimization (e.g., for fiberless optical networking).