What's the minimum number of points I need to measure to find out how much two rectangles are overlapping? This is for a web app, but I think it's a general geometric problem, and almost certainly a solved one:
I have a rectangle $(A)$ and I know its size. I'm trying to figure out if there's another rectangle $(B)$ overlapping mine, and by how much to $25\%$ accuracy. (That is, I want to know if $B$ is covering $0\%$, $0-25\%$, $25-50\%$, $50-75\%$ or $100\%$ of $A$.)


*

*There may or may not be a second rectangle.

*There may be more than one other rectangle.

*The rectangles are all oriented parallel to each other (no rotation).

*I can only test by checking for an overlap at a particular point on my rectangle's surface.


I'm trying to figure out the most efficient possible arrangement of detection points. Ideally, I'd simply be able to count up the number of hits to know the $\%$ in some kind of simple linear way. Something like the image in this overlap detection drawing.
$\hskip{2.8in}$
 A: There are a few domains that treat this kind of thing.


*

*In math, you'll probably only need some simple 2D geometry, but some way more complicated, but related ideas, are: simplicial complexes, gaussian integers and half-integers, lattices, etc.

*In computer graphics/vision, there is...?

*In physical modeling, there is collision detection (probably your best bet).


Just to try to give your problem a concrete formulation,
here are some very simple observations and fundamental questions. 
I imagine your problem is that you have a collection of rectangles $\{A_k\}_{k=1}^n$ in $\mathbb{N}^2$ (i.e. with nonnegative integral coordinates), each centered at $(x_k,y_k)$ and having half-lengths $(a_k,b_k)$, so that $A_k=\{(x,y)\in\mathbb{N}^2 \mid |x-x_k| \le a_k \wedge |y-y_k| \le b_k \}$. Such representations are unique as long as $\forall k: a_k \le x_k,~b_k \le y_k$.
Fundamental questions (the first being, are you working in $\mathbb{R}$ or ${Z}$, continuous or discrete coordinates):


*

*Are you working with continuous or discrete rectangles (i.e. over $\mathbb{R}$ or $\mathbb{Z}$), and are the coordinates signed or unsigned?

*Do all the edges of a rectangle contain points (which can cover those of another rectangle)?

*Do you know $k$?

*Do you know all rectangles?

*Do you know their centers $(x_k,y_k)$ and "radii" $(a_i,b_i)$?


One subtlety with the above definition is that,
in the discrete case,
the $x$ or $y$ coordinates of the center and "radii"
will be half-integers, in $(\frac12\mathbb{N})^2$,
precisely when the full length in that dimension is even.
This amounts to an additional constraint, namely, that
$2x_k\equiv2a_k\pmod2$ and
$2y_k\equiv2b_k\pmod2$.
But the interval endpoints are always integers.
Let us abbreviate this by saying
$A_k=\text{Rect}(x_k,y_k,a_k,b_k)$,
$C(A_k)=(x_k,y_k)$ for the center and 
$R(A_k)=(a_k,b_k)$ for the "radii".
We could then say that an arbitrary point
$P$ is inside $R$ if $|P-C| \le R$,
where this is interpreted as a joint
statement or simultaneous inequality
in each dimension
(so that $|P-C| \not\le R$
and $|P-C| \gt R$ have different meanings).
This definition is equivalent to defining rectangles on $[0,\infty)^2$ by identifying points $(x,y)\in\mathbb{N}^2$ with cells $[x,x+1)\times[y,y+1)\in\mathbb{R_{\ge0}}^2$.
With this identification of $\mathbb{N}^2$ with $\mathbb{R}_{\ge0}^2$,
we can say that $A_k=[x_k-a_k,x_k+a_k  ]\times[y_k-b_k,y_k+b_k  ]$ in the former
space, but that $A_k=[x_k-a_k,x_k+a_k+1)\times[y_k-b_k,y_k+b_k+1)$ in the latter
space.
Let $m$ be your area function on rectangles, i.e. $m(A)=\#(A\cap\mathbb{N}^2)$ is the number of integer points in the rectangle (this formula works also in $\mathbb{R_{\ge0}}^2$ if the rectangles have integral side lengths and are left-closed, righ-open). The intersection of two rectangles $A$ and $B$ is also a rectangle, $AB=A\cap B$, since they are parallel. The overlap is just $m(AB)$.
Given $A_j$ and $A_k$ as above,
their intersection is (non)empty iff
their centers are (not) too far apart
in either dimension:
$$
A_j \cap A_k = \emptyset
\qquad
\iff
\qquad
|x_j-x_k|>a_j+a_k
\quad
\vee
\quad
|y_j-y_k|>b_j+b_k
$$
$$
A_j \cap A_k \ne \emptyset
\qquad
\iff
\qquad
|x_j-x_k| \le a_j+a_k
\quad
\wedge
\quad
|y_j-y_k| \le b_j+b_k
$$
In the case that it is nonempty, the intersection will be given by
$$
\eqalign{
A_j \cap A_k
&=
% why are the parenthesis pair sizes different when using \left & \right?
% \left( [x_j-a_j,x_j+a_j] \cap [x_k-a_k,x_k+a_k] \right)
% \times
% \left( [y_j-b_j,y_j+b_j] \cap [y_j-b_j,y_j+b_j] \right)
  \bigg( [x_j-a_j,x_j+a_j] \cap [x_k-a_k,x_k+a_k] \bigg)
  \times
  \bigg( [y_j-b_j,y_j+b_j] \cap [y_j-b_j,y_j+b_j] \bigg)
\\
&=       [\max(x_j-a_j,x_k-a_k),\min(x_j+a_j,x_k+a_k)] \\
& \times~[\max(y_j-b_j,y_k-b_k),\min(y_j+b_j,y_k+b_k)] \\
}
$$
where, since we are treating endpoints, they are all integral
in the discrete case.
Assuming parallel rectangles and in the discrete case that edges contain points and can therefore cover points from other objects, it will be true that for two rectangles $A$ & $B$, $A$ covers half or more of $B$ iff $A$ (as an object in $\mathbb{R}^2$) contains the center of $B$:
$$m(AB)\ge\frac12m(B) \iff C(B)\in A.$$
Note, in the discrete case, that we must on the RHS treat half-integer coordinates of $C(B)$ as being in $A$ as long as they satisfy (both) the distance inequalities above, i.e. if the point's four nearest integral neighbors lie in $A$.

Actually, the diagram you linked is very illuminating.
If you think about integer-valued vertices as the sample points
each being assigned or identified with a $1\times1$ cell
(say, by a left endpoint rule to use terminology from Riemann sums),
I think you will see that it is a limiting case.
Therefore, the interplay between discrete rasterization
and the more familiar continuous geometry of $\mathbb{R}^2$
comes into play, and you need $25$ sample points to detect
quarter-area overlaps of a $4\times4$ rectangle of area $16$.
