Geometric Algorithm Design and Visualization

这个项目将研究计算几何中的基本几何问题和超大规模集成电路计算机辅助设计中出现的问题。提出了一种新的基于非对称距离度量的Voronoi图模型，并深入研究了该模型的特点和高效的计算算法。研究平面上的双目标优化问题，如约束最大延迟的最短路径树或最小生成树路由问题，具有固定方向的Steiner最小树路由问题，以及拓扑通孔最小化等其他优化问题。不仅将研究这些优化问题的计算复杂性，而且还将开发有效的启发式算法和实现。将采用基于网络的可视化软件工具，帮助设计和传播可用的几何代码。所有软件将用C++和Java编程语言实现，并使用西北大学开发的可视化程序包。这项研究的目标是应用几何技术来解决计算几何以及其他工程领域中出现的问题，特别是VLSI CAD，以增加计算几何对应用领域的实际影响。

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.