# How difficult is to find a small clear round spot on a large sheet contaminated by random dirty dots

The problem arose after a discussion why larger digital camera photo sensors is much more expensive than little bit smaller ones, and the reason was given that it's due to difficulty of finding a larger area spot on a big CCD or CMOS panel.

Consider a large clear white sheet (of a given area $S$, and we may consider it of any convenient non-degenerate shape, such as square or circle) with some black dirt dots on it. The average density of the dirt dots is uniform and known to be $p$ dots per unit area. Somebody wants to find a clear round spot of radius $r$ on it.

Question 1: how difficult is it to find such a spot (and the term "difficult" maybe is defined as "the probability of a random disc being clear?"). How many such non-overlapping spots there are on the sheet on average?

Question 2: how much more difficult is it to find a spot of radius $k\cdot r$ with $k \gt 1$ than a spot of a radius $r$?

When $S\gg s=\pi r^2$, this looks easy, but when $S$ is comparable to $s$, the result is not so obvious.

-

I'll answer the first part of Question 1. I think the second part of Question 1 is probably intractable analytically; and Question 2 is just a special case of the first part of Question 1.

The number of spots on any given area is Poisson-distributed. On a spot of area $s$ with dot density $p$, the expected number of dots is $ps$, so the Poisson distribution is given by

$$p(n) = \frac{(ps)^n\mathrm e^{-ps}}{n!}\;.$$

The probability of the spot being clear is $p(0)=\mathrm e^{-ps}$. Thus, the reason given was correct; finding a clear spot becomes exponentially difficult with the spot's area $s$.

-
So, answer to the second question follows: $p_{s}(n)/p_{2s}(n) = \frac {exp(ps)} {2^n}$. That's interesting - if we relax the initial condition for the spot to be not just clear, but "clean enough", that is, to have no more than $n$ dots (sensors' manufacturers permits small amount of defects), then the difficulty still remains exponential in sensor area $s$, just relaxed by a coefficient $2^n$. –  mbaitoff Jul 11 '11 at 10:38
By the way, what is the valid estimation for (a) number of non-overlapping clear spots, and (b) number of non-overlapping "clean enough" spots? –  mbaitoff Jul 11 '11 at 10:40
On your 1st comment: no, you fixed a factor $2$ but then generalized the result to arbitrary $s$. The dependence on $s$ is with $s^n\mathrm e^{-ps}$, not $2^n\mathrm e^{-ps}$. On your second comment: I don't quite understand what you mean by "the valid estimation". As I wrote in my answer, I think the number of non-overlapping clear spots is probably intractable analytically. –  joriki Jul 11 '11 at 10:49
Cannot understand your objection on my 1st comment. Your formula is valid for any $s$, $p$ and $n$. So if we fix $p$ and $n$, the dependence on $s$ is indeed $s^ne^{-ps}$. Thus, the difficulty ratio between spot area $s$ and spot area $2s$ is as I wrote, $\frac {e^{ps}} {2^n}$, isn't it? On my 2nd comment: what is your analytical opinion about the number of clean spots? Mine is like $\frac {S} {s} \cdot p(0)$ –  mbaitoff Jul 11 '11 at 11:06
1st comment: Yes, that's the difficulty ratio for $s$ and $2s$; my objection was to your conclusion that "the difficulty still remains exponential in sensor area $s$, just relaxed by a coefficient $2^n$". That's not what that difficulty ratio tells us. The difficulty still remains exponential in the sensor area $s$, just relaxed by a factor $s^n$. –  joriki Jul 11 '11 at 11:21