6
$\begingroup$

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.

1 Answers 1

4

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$.

  • 0
    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$.2011-07-11
  • 0
    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?2011-07-11
  • 0
    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.2011-07-11
  • 0
    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)$2011-07-11
  • 0
    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$.2011-07-11
  • 0
    2nd comment: That's probably a good rough estimate. The expected number of clean spots in a fixed arrangement of spots would be $\lambda\frac Ssp(0)$, where $\lambda$ is the packing density, which is $\pi/\sqrt{12}\approx0.9$ for hexagonal circle packing. But since there are many different arrangements for the spots (whose probabilities of being clear are of course highly correlated), the expected number will be strictly more than that.2011-07-11
  • 0
    That estimate is probably better when there are few dots and many clear spots. If there are many dots and few clear spots, the spots no longer have to be tightly packed, which gives them a lot more entropy. Actually, it seems quite plausible that modelling this would lead to a statistical mechanical system with a phase transition between a solid (lattice-ordered) phase at low dot density and a fluid (unordered) phase at high dot density -- interesting :-)2011-07-11
  • 0
    Yes, estimate based on area ratio is good for small number of dots, an very large sheets relative to spots. However, there are very "unfortunate" spot distributions that allows very few clear spots available (or even none). For example, a situation where dots are distributed in vertices of a triangle grid.2011-07-11