Dummy metal fills are inserted in the upper metal layers of a chip to restore planarity of the metal layers and to ensure mechanical robustness of the chip, thereby its performance. Existing tile and window-based metal fill synthesis techniques typically check the metal density of a layer within a square tile window, insert dummy metal shapes in the tile if required, and shift the window by a distance related to the side of the tile to cover the entire layer. As a large number of window positions have to be checked for accuracy, these window based approaches are not efficient. In this paper, we propose a Voronoi diagram-based tessellation for better selection of the positions where metal fills need to be inserted to improve the uniformity criteria. Our method is compared with an existing Monte-Carlo (MC) based fast heuristic using windows on ISCAS'85 benchmarks. Experimental results demonstrate that our method guarantees the same minimum metal density with smaller variation in metal density variation and less coupling capacitance between the metals. © 2012 IEEE.