In this paper, we present a new algorithm to construct a discrete Voronoi diagram based on the Euclidean distance metric in a binary image. The algorithm has linear time complexity and is suited to very large-scale integration (VLSI) implementation due to the use of local neighborhood calculations on reduced bit-width data. A cellular architecture for construction of the diagram is proposed. The proposed architecture has been implemented in VLSI using 0.35 micron 2-poly 3-metal layer complementary metal-oxide-semiconductor technology, and the dimensions of the chip are 3.16 mm × 3.16 mm, with the maximum frequency of operation being 50 MHz.