An efficient algorithm for the largest empty figure problem based on a 2D cellular automaton architecture

摘要

An efficient algorithm for determination of the largest empty figure that can be placed between a set of sites on a plane and its VLSI implementation are presented in this paper. The proposed algorithm is based on the Voronoi diagram in the ϱ1 metric which is established through the time evolution of 2-Dimensional Cellular Automata. The proposed algorithm is fast and efficient, and the 2-Dimensional Cellular Automaton architecture presented in this paper achieves a high frequency of operation. A Von-Neumann neighbourhood processor was implemented on a single VLSI chip using a 1.2 μm Double Layer Metal CMOS technology.