(

*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^{2}, the most efficient solution uses fast matrix multiplication in the preprocessing stage. We give a reduction from matrix multiplication, which shows that in R^{2}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.

## No comments:

## Post a Comment

Type your comment here