Grid Graph Recovery of High-Density Components

Why a Grid Graph Needs More Than an Accurate Density Estimate

A common way to estimate high-density regions is to evaluate a density estimate on a grid, keep locations whose estimated density exceeds a threshold, and connect neighboring retained locations. The resulting graph is simple to compute and inspect. Its connected components, however, represent the components of a population level set only when both the density estimate and the grid resolve the relevant geometry.

There are two distinct sources of error. Estimation error can change whether a grid location passes the threshold. Discretization can miss a narrow bridge, or make two regions appear connected when they are not. A useful analysis therefore starts with a bound that combines both errors, then makes the necessary connectivity and separation conditions explicit.

The Grid Graph and Its Level-Set Bound

Let $D\subset\mathbb{R}^d$ be a rectangular domain, let $f$ be a density on $D$, and fix a threshold $\lambda$. The population level set is $L_\lambda=\{x\in D:f(x)\geq\lambda\}$. Partition $D$ into grid cells of side length $h$, and write $c_Q$ for the center of cell $Q$. Cells along the boundary may be clipped to $D$, but their assigned centers must lie in $D$.

Definition: Given estimated values $\hat f(c_Q)$, retain cell $Q$ if $\hat f(c_Q)\geq\lambda$. The grid graph has one vertex for each retained cell, with an edge between two vertices when their cells share a full $(d-1)$-dimensional face. Its graph components are the connected components of this finite graph. Diagonal corner contact alone does not create an edge.

Assume that $f$ is $L$-Lipschitz on $D$, meaning $|f(x)-f(y)|\leq L\|x-y\|$ for all $x,y\in D$, and that the grid-center errors satisfy $\max_Q|\hat f(c_Q)-f(c_Q)|\leq\varepsilon$. The greatest distance from a cell center to a point in its cell is at most $\rho=\sqrt d\,h/2$. Define the combined error allowance $q=\varepsilon+L\rho$.

Theorem (cellwise level-set sandwich): Under the Lipschitz and grid-center error assumptions above, let $U_h$ be the union of retained cells. Then $$ L_{\lambda+q}\subseteq U_h\subseteq L_{\lambda-q}, \qquad L_t=\{x\in D:f(x)\geq t\}. $$

The inclusions are useful because they separate numerical accuracy from geometric interpretation. The retained cells contain the higher-threshold population set, but cannot extend outside the lower-threshold population set. The width $2q$ of this bracket is an error band around the target threshold.

Bound the density within a retained cell.
If $Q$ is retained, then $\hat f(c_Q)\geq\lambda$, so $f(c_Q)\geq\lambda-\varepsilon$. For every $x\in Q$, Lipschitz continuity gives $f(x)\geq f(c_Q)-L\rho\geq\lambda-q$. Thus $U_h\subseteq L_{\lambda-q}$.

Show that higher-level points are covered.
Take $x\in L_{\lambda+q}$ and let $Q$ be its grid cell. Then $f(c_Q)\geq f(x)-L\rho\geq\lambda+\varepsilon$. The error bound implies $\hat f(c_Q)\geq f(c_Q)-\varepsilon\geq\lambda$, so $Q$ is retained and $x\in U_h$. Hence $L_{\lambda+q}\subseteq U_h$. Together these arguments prove the sandwich. $\square$

When Does the Graph Recover the Components?

The sandwich alone does not establish the number of graph components. A continuous connected set can be too narrow for the grid to represent, and a connected union of cells can have its own connectivity conventions at corners. A component-recovery claim needs assumptions about how the level sets and their grid representations behave.

Definition: Say that a grid is resolving for a level-set component when the retained cells assigned to that component form a nonempty, face-connected graph. Assignment is unambiguous if each retained cell lies wholly within one component of $L_{\lambda-q}$.

Here is a precise sufficient condition. Suppose the components of $L_{\lambda-q}$ are $A_1^-,\ldots,A_K^-$, and those of $L_{\lambda+q}$ are $A_1^+,\ldots,A_K^+$. Assume the higher-level components correspond one-to-one with the lower-level components, with $A_j^+\subseteq A_j^-$. This is a level-set stability condition: moving the level across the error band neither merges nor splits the components. Also assume each retained cell lies wholly in one $A_j^-$. Finally, within each $A_j^-$, assume the retained cells are nonempty and face-connected.

Theorem (grid component recovery): Under the assumptions in the preceding paragraph and the cellwise level-set sandwich, the grid graph has exactly $K$ components, one assigned to each component of $L_{\lambda-q}$ and hence to its corresponding component of $L_{\lambda+q}$.

Proof. Every retained cell lies in $U_h$, and the sandwich gives $U_h\subseteq L_{\lambda-q}$. By assumption, each such cell lies wholly within one $A_j^-$, so no retained vertex is assigned to two different components. Cells assigned to different $A_j^-$ cannot share a face: if they did, their shared face would contain points in both components, contradicting that the components are disjoint. Thus there are no graph edges between different assignments. For each $j$, the assumed nonempty face-connected collection of retained cells is one graph component. There are $K$ such collections, so the graph has exactly $K$ components. The one-to-one correspondence of the lower- and higher-level components supplies the claimed population interpretation. $\square$

The theorem identifies where grid resolution enters: the retained cells within each population component must actually connect. A useful way to verify this in an application is to check that high-density paths have enough clearance from the threshold and are wide enough to be traversed by face-adjacent cells. A component separated from the next one by a positive gap is easier to resolve when the grid is much finer than that gap. Neither positive separation nor a visually plausible plot, on its own, guarantees that every component is represented by the chosen grid.

Worked Example: Calculating the Combined Error Allowance

On $D=[0,1]^2$, consider the density $f(x,y)=0.75+0.5x$. It integrates to one because $\int_0^1\int_0^1(0.75+0.5x)\,dy\,dx=0.75+0.25=1$. Its Lipschitz constant is $L=0.5$: the gradient is $(0.5,0)$, whose Euclidean norm is $0.5$. Use a grid with $h=0.1$, a uniform center error bound $\varepsilon=0.02$, and threshold $\lambda=1$.

In dimension two, the cell radius bound is $\rho=\sqrt{2}(0.1)/2\approx0.07071$. Therefore

q=0.02+0.5(0.07071)\approx0.05536.

The sandwich theorem gives $L_{1.05536}\subseteq U_h\subseteq L_{0.94464}$. For this density, $f(x,y)\geq t$ is equivalent to $x\geq2(t-0.75)$. Thus the higher-level set starts at $x\approx2(1.05536-0.75)=0.61072$, while the lower-level set starts at $x\approx2(0.94464-0.75)=0.38928$. The theorem guarantees that the retained cells cover the first region and remain within the second. It does not, by itself, guarantee a particular graph component count; that conclusion also needs the component and grid-connectivity assumptions.

Worked Component Recovery and a Resolution Failure

Worked Example: Two Components with a Robust Grid Classification

Let $X\sim N(0,1)$ truncated to $[-1,1]$ and renormalized. Its density on this interval is proportional to $\exp(-x^2/2)$; for a transparent grid calculation, instead consider the density $f(x)=1+0.5\cos(2\pi x)$ on $[0,1]$. This is nonnegative and integrates to one, since the cosine integrates to zero. Take $\lambda=1.2$, grid width $h=0.1$, and center error at most $\varepsilon=0.04$.

The grid centers are $0.05,0.15,\ldots,0.95$. At $x=0.05$, $f(x)=1+0.5\cos(0.1\pi)\approx1.4755$, and at $x=0.15$, $f(x)=1+0.5\cos(0.3\pi)\approx1.2939$. Both remain above threshold even after subtracting the maximum error: $1.2939-0.04=1.2539>1.2$. By symmetry, the centers $0.85$ and $0.95$ also remain above threshold. The next centers inward, $0.25$ and $0.75$, have density $1$, and even after adding the error their estimates are at most $1.04<1.2$. The remaining centers between them have density below one. Thus the graph consists of two runs of adjacent retained centers, one at each end of the interval, and has exactly two components. In the continuous domain, $f(x)\geq1.2$ is equivalent to $\cos(2\pi x)\geq0.4$, which also gives two intervals, one at each end. Here the center margin and grid placement make the graph classification unambiguous.

Worked Example: A Narrow Bridge Missed by the Grid

On the unit square, define a density to equal $2$ on the union of two squares $[0.1,0.3]\times[0.4,0.6]$, $[0.7,0.9]\times[0.4,0.6]$, and the thin rectangle $[0.3,0.7]\times[0.445,0.455]$. Set it equal to $208/229$ elsewhere. The high-density region has area $0.04+0.04+0.004=0.084$, so the total integral is $2(0.084)+(208/229)(0.916)=0.168+0.832=1$. It is a valid density.

At threshold $\lambda=1.5$, the population level set is the entire high-density region. The two squares are connected by the thin rectangle, so the level set has one component. Now use a grid of width $h=0.2$, with centers at coordinates $0.1,0.3,0.5,0.7,0.9$ in each direction. The bridge lies between $y=0.445$ and $y=0.455$, so no grid center lies in it. The high-density centers in the left square, such as $(0.1,0.5)$, and in the right square, such as $(0.9,0.5)$, are retained, but the center $(0.5,0.5)$ lies outside the high-density region and is not retained. The graph therefore has two components, although the population level set has one. The failure is geometric, not an estimation error: even exact density values cannot make this grid resolve the narrow bridge.

Common Pitfall: Treating Uniform Accuracy as a Topology Guarantee

A uniform error bound is valuable, but it does not alone ensure component recovery. The sandwich theorem controls where retained cells can lie and which higher-level points must be covered. It does not ensure that the retained cells inside a component are connected. Nor does it ensure that the level sets at $\lambda-q$ and $\lambda+q$ have the same component structure.

Incorrect reasoning: “The estimated density is uniformly close to the true density, so its grid graph has the right components.”
Why it fails: A bridge can be narrower than the grid spacing, as in the preceding example. Also, small vertical errors can change threshold decisions near $\lambda$, where the density has little margin.
Correction: Combine the error allowance $q=\varepsilon+L\sqrt d\,h/2$ with level-set stability across that band, adequate separation between distinct components, and a grid-connectivity condition for the retained cells.

When the density estimate is accurate but the grid is coarse, reducing estimation error alone may not help. Refining the grid reduces the within-cell term $L\sqrt d\,h/2$, but may increase computational cost. Conversely, an extremely fine grid does not compensate for a level set whose components merge or split across the uncertainty band. Reporting the threshold, grid spacing, error bound, adjacency convention, and geometric assumptions makes a component-recovery claim interpretable and reproducible.

Key takeaway: Grid graph recovery is a joint estimation-and-resolution problem. The cellwise sandwich quantifies the combined density and grid error; component recovery additionally requires stable population components and a grid that represents their connectivity without joining distinct components.

Check Your Understanding

Use the definitions and conditions above to answer these questions.

For a grid in dimension $d$, explain why the cell-center radius is at most $\sqrt d\,h/2$.
If the uniform center error is $\varepsilon$ and $f$ is $L$-Lipschitz, what is the combined allowance $q$, and what are the two level-set inclusions?
Why does the sandwich bound not, by itself, prove that the grid graph has the same number of components as $L_\lambda$?
In the narrow-bridge example, is the component-count error caused by density estimation error or grid resolution? Explain.
Name two geometric or grid-connectivity conditions needed, in addition to a uniform estimation bound, for component recovery.