Geometric Algorithm Design and Visualization

点击翻译按钮获取中文摘要

Fundamental geometric problems in computational geometry and those that arise in VLSI computer-aided design will be investigated in this project. A new model of Voronoi diagram based on distance measures that are not symmetric is proposed and its characteristics and efficient algorithms for its computation will be thoroughly studied. Bi-criteria optimization problems in the plane, such as shortest path tree or minimum spanning tree routing with constraints on maximum delay, Steiner minimum tree routing with fixed orientations, and other optimization problems such as topological via minimization will be investigated. Not only the computational complexity of these optimization problems will be studied, but also efficient heuristics and implementations will be developed. Web-based visualization software tools that help design and dissemination of usable geometric codes will be implemented. All software will be implemented in C++ and Java programming languages with the use of visualization package developed at Northwestern University. The goals of this research are to apply geometric techniques to tackle problems that arise in computational geometry as well as other engineering fields in general and VLSI CAD in particular, in order to increase the real impact of computational geometry on applied areas.