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.