Dynamic connectivity in digital images
- Author(s): Eppstein, David
- et al.
We show that any algorithm that maintains the connected components of a digital image must take Ω(log n/log log n) time per change to the image. The problem can be solved in O(log n) time per change using dynamic planar graph techniques. We discuss applications to computer Go and other games.