Development of Geometric Clustering Algorithms and Applications to VLSI Design

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

Grouping similar objects is called cluster analysis. There have been considered a lot of algorithms. When we formulate this problem as a problem in Graph Theory, it may often become NP-complete. Therefore, we rely on heuristic algorithms. In this research we first presented an algorithm for mapping objects into points in the plane so that similar objects are placed closely, based on Principal Coordinate Analysis. Then, applying Geometric Transform, points are mapped into lines. Using Topological Walk Algorithm developed in the research, we can examine all possible regions defined by those lines. This corresponds to examination of all possible partitions of those points in the dual plane. The idea was applied to Circuit Partitioning in VLSI design.