Geometric Algorithm Design and Visualization

计算几何中的基本几何问题和VLSI计算机辅助设计中出现的基本几何问题将在本项目中进行研究。提出了一种新的基于非对称距离测度的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.