BOUNDARY-OPTIMAL TRIANGULATION FLOODING
Richard J. Nowakowski, Norbert Zeh · International Journal of Computational Geometry & Applications · 2006
Given a planar triangulation all of whose faces are initially white, we study the problem of colouring the faces black one by one so that the boundary between black and white faces as well as the number of connected black and white regions are small at all times. We call such a colouring sequence of the triangles a flooding. We prove that a flooding with boundary size [Formula: see text] and [Formula: see text] regions can be computed in [Formula: see text] time. We also prove that it is in general impossible to guarantee boundary size [Formula: see text], for any ∊ > 0, and a number of regions that is o( log n), where n is the number of faces of the triangulation.