I'm working on a optimization problem of finding a region maximizing certain objective function, I'm using a set of pixel coordinates to keep track of the region, and for each step I'll add or remove a pixel at boundary to see whether the objective function increase or not. I hope the region to be connected, are there any data structure that could quickly decide whether removing a pixel would make the region disconnected? Here we assume a pixel is connected to its four neighbors.
And a parallel question: what if I hope the region is always simply connected? By simply connected I mean there is no hole, and adding a pixel may create a hole.
You can look at the configuration of a 3x3 neighborhood before and after removing a pixel (or adding a pixel) and decide if that action will change the Euler characteristic of the object it's connected to. The Euler characteristic tells you how many object and how many holes there are.
If there are between 1 and 7 set pixels in the 3x3 neighborhood, excluding the center pixel, and they are simply connected, then adding or removing that center pixel will not change the Euler characteristic (i.e. not add/remove a hole or add/remove an object), assuming an 8-connected object (for a 4-connected object, there are fewer configurations for which this is true, it's easy to work them out).
Typically one would have a table with the 256 possible configurations of those 8 pixels, you encode the configuration as an index into the table (for example by going clockwise around starting at the top-left pixel, reading the pixels as an 8-digit binary number). It is then very quick to look up whether you can remove (or add) a pixel in a given location.
Look for a standard implementation of the skeletonization algorithm or the morphological thinning. These two operations perform this exact same check on each pixel before removing it, they both need to preserve the Euler characteristic. For example, see this table in scikit-image.