Interesting CS/Math problem

For the second, I think you mean minimum connected region...otherwise it's somewhat trivial :) though in that case, the box at location (5, 7) fifth column, seventh row, could be colored white without violating the connected property.

Off the top of my head I can't think of a really efficient algorithm for those, but these kind of problems just scream dynamic programming. Let me look around a bit...

edit: I suppose you could try reading this: http://citeseer.ist.psu.edu/rd/19535151%2C382311%2C1%2C0%2CDownload/http%3AqSqqSqwww.ics.uci.eduqSq%7EeppsteinqSqpubsqSqEppOveRot-DCG-92.pdf

For the second problem, representing each cell in the grid as a node in a graph (each one connected to four neighbours, excepting the edges of course), then removing the yellow nodes, then pathfinding from any red node to all other red nodes and recording the nodes you touch in the process will give you the solution, I think.

For the first problem, does it have to be a convex polygon?

For the first problem if you wanted a convex polygon you could use a technique know as "plastic wrapping". If you used the four points in each cell it would look something like this:



Edit: See this, page 28/29

Is this not the same problem as the 'convex hull' problem encountered all the time in graphics?

Yes, the convex hull algorithm should solve the first problem

Quote:

Original post by gabzuka Yes, the convex hull algorithm should solve the first problem

And it might be a good starting point for the second problem?

I realized that I was solving the wrong part of the problem! Here is the real hard part: Given a grid of squares that are white (blank), yellow and red, how can you classify them into different populations?

For example, here I have produced an image of a yellow population with 3 different red populations, R1 (top left), R2 (top right), R3 (bottom). How could I figure out which red squares belong in each of R1, R2, and R3?



I have a feeling this might have to do with computer vision?

Yes, this sounds like computer vision (although your example is quite simple). You could try to use a discretized level set representation of an active contour, with all red tiles inside, all yellow tiles outside, as many tiles as possible outside, while maintaining some level of continuity.

I still dont get why it matters wether a square is yellow or white.

Edit: Oh, duh, there are no yellow tile inside the convex hull group of reds, correct? Ah, this greatly simplifies the problem.


Edit: how do you put a line through a word in html?

I'd have to agree with using something similar to the path finding alogithm for the 2nd problem only Shortest distance to any red block from its nearest neighbor and limit to searching farther than 3 blocks. That would limit the program from selecting a red block from other sections of the picture and still limit the number of white spaces it connects to. Another way to prevent it is from keeping it from crossing certain horizontal vertical asymptotes. Probably better off using the 3 block restriction.

Not sure if this will help any but thought I'd chime in.

Quote:

Original post by AndreTheGiant Edit: how do you put a line through a word in html?

some text
some text

Could you not do a simple square-by-square algorithm thusly:
- If a red square is within x steps of an already-assigned red square, it is part of the same population
- otherwise, make a new population and assign the square to that
- if an assignment leads to two populations having members within x steps of each other, merge the populations.
?

The last step should solve the problem of a U-shaped population when you do a simple row-by-row traversal.

Color white squares red or yellow according to which of these colors is closest to the square. Then use a fill to separate regions.

This is a self-learning problem in AI often known as "Spectral Clustering"

There a nice detail/implementation of it here

Here's something off the top of my head for the second problem:
1) go through all the pairs of red pixels that are on the same line or coloum and check if the pixel(s) between them is white. if it is then color it red and store the position of the new red pixel(if there're more than one than do this for all of them).
2)do the same thing as in 1 but only with the new pixels.
3)repeat 2 untill there're no new pixels.

in the image shown this would stop after the first pass.
this seems relativly efficiant - especially if there's some kind of partitioning going on.

EDIT: for the new problem i guess that you'd have to add to step 1 that if a row or coloum has a yellow pixel than don't fill in anything on the row.
after filling in everything it's easy to divide them into groups. for example, you could chose one of the red pixels (after filling everything in) and call it group A, then recursivly call everything touching it A and soon the whole group will be marked as A. when this is done call an unmarked pixel B and do the same thing.