Color Full

How full of color does something have to be before it's called colorful?

(Is this a nonsense question? No.)

Here's a cat with color. There's a bit of black and a bit of white, along with lots of blues and greens.

Here's a bit more color, on a cow. More orange and green and more black.

Here are a few more colors, and more brightness. Less green, more black. This is a goat, not a dog.

Here is a raven - there seems to be a bit "more color" and fewer colors. If you see what I mean.

How many colors are in these paintings? One way to count is to put a grid over it, and decide which is the primary color in each square. Make the squares small enough, then count the colors.

Of course you would need a lot more squares than this, and lots of time and good eyes.

Here's a mathematician's viewpoint on how to do it with a computer:

Let P be a set of n points in R^d, so that each point is colored by one of C given colors. We present algorithms for preprocessing P into a data structure that efficiently supports queries of the form: 

Given an axis-parallel box Q, count the number of distinct colors of the points of P ∩ Q. 

We present a general and relatively simple solution that has polylogarithmic query time and worst-case storage about O(n^d). We then present several techniques for achieving space-time tradeoffs. In R², the most efficient solution uses fast matrix multiplication in the preprocessing stage. We give a reduction from matrix multiplication, which shows that in R² our time-space tradeoffs are close to optimal in the sense that improving them substantially would improve the best exponent of matrix multiplication. 

Finally, we present a generalized matrix multiplication problem and show its intimate relation to counting colors in boxes in any dimension.

We DO NOT cover this in Excel Math, just in case you were wondering. And I didn't make up any of the words - that's how some mathematicians communicate ...

FYI - The pictures are by Joe Nyiri. He teaches art to kids at schools and at the San Diego Zoo.