2
$\begingroup$

This is a purely theoretical question: among the known flood fill algorithms, there is one which does not require any dynamically-sized data structures, explicit or implicit: the so-called Walk-based filling, expressed there in structured English, e.g.

...
while front-pixel is empty do
    move forward
end while

jump to START

MAIN LOOP:
    move forward
    if right-pixel is inside then
        if backtrack is true and findloop is false and either front-pixel or left-pixel is inside then
            set findloop to true
        end if
        turn right
PAINT:
        move forward
    end if
START:
    set count to number of non-diagonally adjacent pixels filled (front/back/left/right ONLY)
...

An attempt to implement that algorithm has revealed that while it is quite clever, it is not robust. For example, given a herringbone pattern,

 *********
 **   *  *
 *  *   **
 * *...* *
 *  .*.. *
 ** ..*. *
 *  *...**
 * *   * *
 *********

if the starting point is one of the locations marked with a period, the algorithm goes into an infinite loop.

Is there a known robust O(1)-space deterministic (apparently, it has to be mentioned) flood fill algorithm? What would be its time complexity?

$\endgroup$
15
  • $\begingroup$ What is your definition of "robust" and how does it differ from correctness on all possible inputs? $\endgroup$
    – D.W.
    Jul 29, 2022 at 3:46
  • $\begingroup$ @D.W. In the context, I've used "it is not robust" in the sense "it cannot cope with some of the inputs" (as opposed to "it is not accurate" if the algorithm always terminates successfully, but does not always produce the correct result). I meant to ask, is there any O(1)-space algorithm which is correct on all possible inputs, but the question if there exists a fix of the "Walk-based filling" algorithm, is also of interest. $\endgroup$
    – Leo B.
    Jul 29, 2022 at 6:49
  • 1
    $\begingroup$ Don't confuse the algorithm principle (possibly expressed by a textual description or informal pseudocode) and a concrete program that implements it. Bugs are not excluded. Also check if your region is four-connected. $\endgroup$
    – user16034
    Jul 29, 2022 at 12:35
  • $\begingroup$ @YvesDaoust Unless there is a readily available implementation of the algorithm in a programming language, which is verifiably free from the bug, the question stands. No matter how the region looks like, the algorithm must not loop forever. $\endgroup$
    – Leo B.
    Jul 29, 2022 at 20:36
  • $\begingroup$ You are wrong. If the algorithms mandates a four-connected region, you must not run it on a region that is not, or you get UB. $\endgroup$
    – user16034
    Jul 29, 2022 at 20:41

2 Answers 2

2
$\begingroup$

Well, purely theoretically... It can be done in $O(1)$ space1 using some well-known techniques, though that may be like firing a cannon at sparrows. I will describe a slightly cumbersome and overengineered, but comprehensible solution in $O(\log n)$ space1, where $n$ is the board area, and then give a link that promises a constant space solution.

1 Space complexity can be measured in bits or in words. They typically differ by the factor of $\log n$. Space complexity classes usually are defined in terms of bits, and the algorithm cited by the author is constant-space in terms of words. I will use words complexity unless stated otherwise.


The core idea of a log-space algorithm is to iterate through cells of a given connected component in order of decreasing shortest path distance to the starting cell. Painting cells in this order guarantees that our connected component will never split into two parts and we will eventually paint it all.

First, we show that the predicate $DistanceAtMost(s, t, k)$, defining pairs of vertices ($s, t$) in an undirected graph such that distance between $s$ and $t$ is at most $k$, is computable in $O(\log n)$ space.

$DistanceAtMost(s, t, 1)$ is trivial. For $k > 1$, $$DistanceAtMost(s, t, k) = \bigvee\limits_w DistanceAtMost(s, w, \lfloor k \rfloor) \wedge DistanceAtMost(w, t, \lceil k \rceil).$$

To compute the predicate for given $s$, $t$, $k$, we enumerate all intermediate vertices $w$ independently check for paths from $s$ to $w$ and from $w$ to $t$ recursively. Recursion has $O(\log n)$ depth and $O(1)$ memory is required at each level (we need to keep a counter for $w$ and remember if current recursive call is computing the left or the right part of the conjunct). Thus the predicate is computable in $O(\log n)$.

Second, we define $$DistanceIsExactly(s, t, k) = DistanceIsAtMost(s, t, k) \wedge \neg DistanceIsAtMost(s, t, k - 1).$$

Now we are ready to solve the original problem. Let $(x_0, y_0)$ be the initial cell. We iterate $k$ from $n$ to $1$ and, for each cell $(x, y)$, check that distance between $(x, y)$ and $(x_0, y_0)$ is exactly $k$ (assuming that moves are only allowed by cells of a certain color). If so, we paint $(x, y)$ with the corresponding color.

Note that painting the furthest cell will not change shortest distances to other cells, so the order of iterating through $(x, y)$ pairs does not matter.

The time complexity is $O(n^{\lceil\log n\rceil})$ for one recursion call times $O(n^2)$ for iterating through distances and cells at the outer loop, giving $O(n^{\lceil \log n \rceil + 2})$.


To get a constant memory algorithm (or $(O\log n)$-bit memory) we need to dive into the deep CS. There is a rather recent (2004) breakthrough result showing that ST-connectivity in undirected graphs is solvable in log-space (bits). It proves the equivalence between $L$ and $SL$ complexity classes, where $L$ is a class of problems solvable in log-space and $SL$ is a class of problems log-space reducible to $USTCON$, the problem of determining if two vertices of an undirected graph belong to the same connected component. See Wikipedia page on SL for details.

It is not obvious to me if $DistanceIsExactly$ belongs to $SL$, but we can try different approach: iterate through cells in any order and paint the cell $(x, y)$ if it is not cutpoint, that is, removing it does not introduce new connected components. Checking it is quite simple: $(x, y)$ is not a cutpoint if removing it does not change connectivity between $(x_0, y_0)$ and $(x', y')$ for any $(x', y')$.

Also, the authors of the mentioned paper present, as stated in the abstract,

a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph.

However, I don't know if their algorithm still works if the graph is modified during traversal.

Regarding time complexity, Wikipedia page on SL claims $64^{32} \log N$ memory and $O(n^{64^{32}})$ time for the algorithm, which is completely impractical.

$\endgroup$
5
  • $\begingroup$ That was fun! Although I wouldn't call this algorithm "working", for the reasons you've mentioned. $\endgroup$
    – Leo B.
    Aug 16, 2022 at 1:47
  • $\begingroup$ @LeoB. It is still robust, however. $\endgroup$ Aug 16, 2022 at 1:51
  • $\begingroup$ It appears that you have doubts about its robustness as you say "I don't know if their algorithm still works if the graph is modified during traversal". Please note that the walk-based algorithm would be no worse than O(n^3), it it always worked. $\endgroup$
    – Leo B.
    Aug 16, 2022 at 5:29
  • $\begingroup$ @LeoB. The approach that paints non-cutpoints one by one is robust, it uses only st-connectivity routine from the paper. The part you quoted refers to another algorithm from the paper, the one that traverses the graph out of the box. So I presented one working approach and noted that there may be another one based on the paper, but I'm not sure about that another one. $\endgroup$ Aug 16, 2022 at 10:27
  • 1
    $\begingroup$ I see. I take that as an indication that the task the author of the walk-based algorithm has tried to solve was pretty much unsurmountable, and there is no chance to fix the walk-based algorithm to make it robust and to keep or improve its current time complexity. $\endgroup$
    – Leo B.
    Aug 16, 2022 at 16:38
0
$\begingroup$

This is an algorithm I came up with, so I'm not sure that is was known before. It is essentially a modification of the walk-based filling method that you mentioned. I'll give a high-level description, with possibly more details to come later.

EDIT...Please see the edit below


The idea is that we will possibly divide the original region to fill into at most 2 regions. We initially start to go clockwise around the initial fill point, although we could have just as easily gone counter clockwise. (If the original fill location is surrounded by filled pixels, we are done.) It also doesn't matter if we go to the right, left, up, or down. The main idea is that we start circling around going clockwise. So again, we are proceeding around the original fill pixel:

**********
*        *
*  432   *
*  501   *
*  6     *
*        *
**********

Here I numbered the starting position with a 0 and numbered the next selections in increasing order.

The trick is that the algorithm will most likely have to cut itself off:

**********
*    3   *
*  **21  *
*  ***0  *

When it gets to position 3, notice that we've split the original region into 2 regions that both need to be filled. So we will mark the split with an "o", and continue, knowing that we now need to fill 2 regions:

**********
*  543o  *
*  **21  *
*  ***0  *

Eventually, we will either come to another split, or we will completely fill one of the regions (in this case, the region on the left).

If we completely fill one of the regions, we can then continue to fill, starting at the point we marked "o". Otherwise, we come to another split. The idea is to record the last few positions we were at as we go along. Now that we've come to another split, we backtrack to where there was no second split, and mark this location as the next location to work on. Then, we go back to the first marked location, and continue on.

The essential idea is that we go back and forth between the 2 regions, making sure that we never create a third region to fill.


EDIT

The idea is instead to continually circle around clockwise, trying to fill locations whenever they do not divide the current region into 2 regions.

So, for example, consider the following image, where we start at "0" and fill in the numbers in order:

**********
*        *
*  456   *
*  .01   *
***.32   *
*        *
**********

Here we skip the locations marked with a period, because they have the potential of splitting the region into two regions. We take care to proceed along the inside wall. So to continue with this example, we would fill:

**********
*        *
* a4567  *
* ..018  *
***.329  *
*  ....  *
**********

Note that once we get to 9, we stay to the inside, proceeding clockwise, over the periods, and skip some more periods. We do not fill the periods. We eventually arrive at "a" where we again fill.

There's another thing that we have to do. Proceeding again as in our example, we fill:

**********
* ...... *
* a4567b *
* ..018c *
***.329d *
*  ....  *
**********

Here we've skipped and then filled "b", "c", and "d". Next we come to a location that we will not fill. The logic here is that any time we come to a location that we do not fill, we record that position. Then, if we continue cycling through the unfilled positions and we come to this recorded or marked position, we know that the area surrounding area is only one pixel wide.

We now continue clockwise around the filled region, not filling anything, but seeing if there are any forks or branches where there is more than one direction to fill. If there is, we:

  1. Go through the branch, away from the current region we were cycling through, still without filling anything.
  2. We mark or record where we start in this new region.
  3. Cycle clockwise in this new region, seeing if there is anything to fill.
  4. If there is, and it doesn't split the region, we fill it.
  5. Finally, we cycle through until we again arrive at the marked region.
  6. We mark the other branch, so that we will come back to it.
  7. We then proceed to fill the original fork we took, so that it does not split the region into two regions.
  8. We go back to the second region we marked, which is the other fork.
  9. Repeat until there are no more forks, then fill the rest.

If there were no forks around our recently filled region, we fill the remaining pixels and we are done.

This procedure should ensure that there are never more than 2 regions to fill.


This should work. Of course, there's a lot of details to keep track of.

$\endgroup$
2
  • $\begingroup$ Superficially, this looks promising, as it is more or less the walk-based algorithm with a "bird's eye" view. However, the author(s) of the walk-based algorithm likely believed that their algorithm should work in all cases, which proved to be wrong. Thus, implementation and testing are required to validate your new algorithm. $\endgroup$
    – Leo B.
    Aug 12, 2022 at 21:38
  • $\begingroup$ @LeoB.: Programming it is the tough part. I'm trying to get a bird's eye view of the problem. I keep thinking that the main concern is when there is a branch or fork. I think that if we can handle all of the cases when this happens, we may have a good shot at a better proof. $\endgroup$
    – Matt Groff
    Aug 12, 2022 at 22:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.