Tight Bounds for Point Recolouring.
Yurai Núñez Rodríguez, David D. Rappaport · Canadian Conference on Computational Geometry · 2006
In their paper on delineating boundaries from geographic data, Reinbacher et al. [9] use a recolouring method to reclassify points so that the boundaries that separate points of different colours become more reasonable. They show that an iterative recolouring method converges after a finite, but exponential, number of steps. They also give, as an example, a triangulated point set with a specified re-colouring sequence that uses Ω(n2) recolourings. In this note we revisit this recolouring problem and obtain a matching O(n2) upper bound.