Development of Geometric Clustering Algorithms and Applications to VLSI Design

将相似的对象分组称为聚类分析。已经考虑了很多算法。当我们把这个问题表述为图论中的一个问题时，它可能经常是np完全的。因此，我们依赖启发式算法。在这项研究中，我们首先提出了一种基于主坐标分析的算法，将物体映射到平面上的点，从而使相似的物体被紧密放置。然后，应用几何变换，将点映射成线。使用本研究开发的拓扑行走算法，我们可以检查这些线所定义的所有可能区域。这对应于对偶平面上这些点的所有可能分区的检查。该思想被应用于VLSI设计中的电路划分。

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.