Universal Support Theorems for Resilient Coverage

Introduction

Coverage design asks three different questions. Is a specified target covered? Which failures destroy that coverage? Which design or protection policy meets a quantitative requirement? Computing the topology of the union of footprints answers part of the first question but not the target question itself, since a contractible covered region can be disjoint from the asset that must be monitored.

We work in a finite model in which all of the geometry can be certified exactly. Physical footprints are closed disks, the target is a finite union of closed nondegenerate triangles, and failure rules are monotone with respect to additional functioning contacts. In this model one canonical geometric certificate connects exact failure budgets, common-radius design, placement uncertainty and the assignment of contacts to fault domains.

Two certificates

For a point $x$ of the target $T$, let $S(x)$ be the set of contacts whose footprints contain $x$. Define

where Min removes every strict superset of another member. For the regular closed targets considered here, every member has a representative away from all disk and target boundaries, and a vertical-slice construction produces a rational representative for each member using only exact sign decisions.

The first certificate is this antichain together with its witnesses. If $\mathcal{F}$ is a downward-closed family of allowed failures, then

One geometric computation therefore answers every such failure query. The antichain is the minimal-cut family of the target-coverage reliability system in the sense of Barlow and Proschan [19]; its geometric origin attaches an explicit target location to each cut.

The second certificate concerns common-radius design. Fix sites and target and let all primitive disk radii equal an unknown $r$. We construct a finite set $Q_T$ of rational points, independent of the winning rule. For every monotone rule $w$ that wins on the full contact set, put

Then the critical radius satisfies

The support set consists of target vertices, bisector–edge intersections and three-site circumcenters, $O(n^3+n^2h+h)$ points in all, and it serves all rules and all common radii at once. In dimension $d$ a maximiser on an $f$-dimensional face of the target is fixed by at most $f+1$ sites.¹

2020 Mathematics Subject Classification. Primary 68U05; Secondary 52A41, 90B25, 05C65, 55U10. Keywords. support theorem; sensor coverage; monotone failure rules; resilience certificates.

The LaTeX source and the finite checks of the worked examples are archived on Zenodo, release v1.1.1, link.

The structural part identifies the canonical antichain, proves that it is the smallest certificate answering all downward-closed failure queries, describes its behaviour under monotone label maps and relates the geometry to nerve and Dowker models. The general support theorem covers functions with a common continuous convex part and affine differences; its finite support set works for every monotone rule and every common convex term. The radius function is a lattice polynomial in the contact distances [21, 22].

The analytic part gives exact arithmetic, finite procedures, uncertainty reductions and optimisation certificates. For product uncertainty sets, robustification commutes with every monotone Boolean contact rule, so independent displacement balls reduce to disk erosion and independent polygonal displacement sets reduce to finite intersections of disks at their vertices. Protection allocation is a linear program whose optimum is certified by rational primal and dual vectors.

The worked examples derive coverage, failure budgets, wiring choices and uncertain placement in exact arithmetic. In the four-corner example, changing the domain assignment changes the coverage reliability from 81/100 to 99/100 at domain failure probability 1/10, with positions, radii and contact count unchanged; the squared radius needed to survive the loss of one domain drops from 89/25 to 68/25.

Related work

Arrangements of algebraic curves and exact geometric predicates are standard tools in computational geometry [16]. Coverage tests based on circle intersections and local geometry are due to Huang and Tseng and to Wang et al. [17, 18], and $k$-coverage via generalised Voronoi diagrams to So and Ye [29]. Homological sensor criteria and multicover nerves are developed in [3, 4, 5, 9, 10, 11]; we include the maps and proofs we need because the failure semantics and boundary conventions matter for the certificates.

Minimal cut sets and structure functions belong to reliability theory [19]. Cover decomposition and polychromatic hypergraph colouring are the natural setting for fault-domain assignment [20]. Max–min functions built from monotone logic are lattice polynomials [21, 22], and Boolean combinations of balls with generalised Voronoi decompositions appear in the work of Csikós [25]. The protection program uses linear programming duality, the treatment of uncertain geometry follows robust optimisation [23], and marginal-only probability bounds are instances of Hailperin’s logical probability programs [24].

What is new here is the support theorem for all monotone rules with a shared convex term, the canonical antichain with rational witnesses, the exact uncertainty reductions and the radius–budget frontier, combined under one failure interface. The contact-intersection model goes back to [1]; the separation of exact predicates from continuous target certificates follows [2]; related topological constructions appear in [13, 15] [14].

Conventions

All planar targets are finite unions of nondegenerate closed triangles with rational vertices. They are regular closed, $T=\operatorname{int}\overline{T}$, and may be disconnected or have holes. Wire targets and isolated points require a lower-dimensional treatment and are excluded from the full-dimensional sampling theorem.⁴

Disk centres and radii are rational. Masks retain physical contact labels, including coincident footprints. Homology is over $\mathbb{F}_2$ unless another field is specified; the target certificates do not depend on the coefficients. The appendices contain the comparison homotopies, the closed-cover chain argument, arithmetic derivations, dual certificates, worked examples and boundary counterexamples. Every statement is proved in the text.

Failure families and surviving regions

The word “winning” refers solely to survival of the prescribed failure model. It does not encode a probability, sensor independence or a clinical performance measure.

1. $x$ remains covered after every failure $F \in\mathcal{F}$;

2. $S(x) \notin\mathcal{F}$;

3. some $\sigma\subseteq S(x)$ is a minimal member of $\mathcal{W}$.

Consequently, with $D_\sigma= \bigcap_{i\in\sigma} D_i$ and $\mathcal{P}_{\mathcal{F}} = \{\sigma\in N : \sigma\notin\mathcal{F}\}$,

where empty geometric intersections contribute nothing.

Proof. Failure of coverage at $x$ after deleting $F$ means precisely that every active contact is deleted: $S(x) \subseteq F$. If $F \in\mathcal{F}$, downward closure then gives $S(x) \in\mathcal{F}$. Conversely, if $S(x) \in\mathcal{F}$, the allowed choice $F = S(x)$ deletes every active contact. This proves the equivalence of the first two statements. In a finite upward-closed family every member contains a minimal member, and any set containing a winning set is winning. This proves the third equivalence and both union identities. □

Proof. For each $i \notin S(x)$, closedness gives an open neighborhood of $x$ disjoint from $D_i$. Intersect these finitely many neighborhoods to obtain an open set $U$ in which no new active label can appear. Regular closedness implies $U \cap\operatorname{int} T \ne\varnothing$. A finite union of disk boundaries and target edges has empty interior, so it cannot exhaust this nonempty open set. Choose $y$ outside it. The active labels of $y$ are all in $S(x)$. In the disk setting, the remaining open set contains rational points by density of $\mathbb{Q}^2$. $\square$

For the first general statement, the avoidance assertion uses that the finitely many boundaries are closed with empty interior, hence nowhere dense. Disk circles and target edges satisfy this condition. No claim about arbitrary nonclosed sensing footprints is needed.

several primitive disk constraints, let its output bit be one exactly when all its primitive bits are one. This conjunction map is monotone and is used for uncertain placement in § 1.7.

Proof. A deletion $F$ destroys coverage precisely when it contains a realized active set, and hence when it contains some antichain member. Nonnegative costs give $c(F)\ge c(A)$. Conversely deleting $A$ removes every active contact at its witness. The strict budget inequality follows because a deletion of cost exactly $\kappa_T(c)$ is allowed when $B$ reaches that value.

For unit costs, the maximum guaranteed number of arbitrary contact losses is $\min_{A}|A|-1$, provided the target is initially covered. For a domain partition, apply Theorem 3.6 first and use one cost per domain. The case $\kappa_T=0$ is not rounded up: it means that no nonnegative budget guarantee holds, either because the target is already uncovered or because a zero-cost cut is available.

An exact construction with rational target witnesses

We now construct the certificate of Theorem 3.3 by vertical slices. Its witness list can be checked by rational point membership alone.

Critical abscissae

Include the following real numbers in a list $X$:

1. the first coordinates of every target vertex;

2. the leftmost and rightmost first coordinates $c_{i,x}\pm r_i$ of each disk;

3. the first coordinates of every intersection of two distinct supporting circles;

4. the first coordinates of every intersection of a circle with a target-edge segment;

5. the first coordinates of every intersection of two target-edge segments.

Remove duplicates and numbers outside the horizontal span of the target. Pairwise coincidences create no infinite list: coincident circle boundaries are represented once for ordering, while contact labels remain distinct; overlapping collinear segments need only their endpoints. Their order does not exchange inside an open slab.

There are $O((n+h)^2)$ listed numbers. Each is rational or has the form $a+b\sqrt{d}$ with $a,b,d\in\mathbb{Q}$ and $d\ge0$. Circle–circle formulas are derived in § 2.5. For a segment $p+t(q-p)$, circle intersection is a quadratic equation in $t$, retaining roots in $[0,1]$. Segment intersections have rational coordinates.

For each consecutive pair $\alpha<\beta$ in $X$, choose a rational $x_0\in(\alpha,\beta)$. The vertical line at $x_0$ meets a circle, when appropriate, at

and a nonvertical target edge at a rational ordinate. Sort these ordinates exactly, remove duplicate values and choose a rational ordinate between every consecutive pair. Test the resulting point for membership in the target interior and, if retained, compute its exact contact mask.

The target is bounded, so every interior component of its vertical section is bracketed by target-edge intersections. Sampling the two unbounded ordinate intervals is unnecessary. Vertical target edges lie on critical abscissae; their omission from generic sections is justified by Theorem 3.1, rather than by assuming they have no target points.

Proof. Between consecutive critical abscissae, no circle appears or disappears in a vertical section, no target-edge segment begins or ends, and two section curves cannot exchange their order. Such an exchange would require an intersection whose first coordinate belongs to $X$. Equal section curves can persist, as with coincident circles or overlapping segments; keeping one ordinate for a persistent equality leaves every open band represented.

Thus each open ordinate band continues through the slab without a boundary crossing, and its contact labels and target membership are constant. Choosing one rational point per band gives those labels exactly. Conversely every two-dimensional target cell has an open horizontal projection, which cannot be contained in the finite list $X$. It therefore meets some open slab and one of its bands. Its mask is among the samples. Theorem 3.3 identifies the minimal masks with $\mathcal{A}_T$. For an activation map, apply Theorem 3.6, or evaluate that map on every sample before minimalization.

Comparing two quadratic numbers

Numerical square roots are not needed even to sort the critical coordinates. Let

Set $A=a-c$, $U=A+b\sqrt{h}$ and $V=d\sqrt{k}$. We seek the sign of $U-V$.

Proof. The cases with different signs or both zero are immediate. When $U,V$ are both positive, squaring preserves their order, and $U^2-V^2$ is the expression in parentheses. When both are negative, their order is the reverse of the order of their squares. This gives the factor $s$ and proves the formula, including equality. The sign of $U$ uses one radical, and the sign of $V$ is the sign of $d$ unless $k=0$.

This test detects equal values with different representations, such as $\sqrt{8}=2\sqrt{2}$. It avoids an interval-refinement loop that would never separate two equal algebraic numbers.

Constructing a rational point between algebraic endpoints

For $h=p/q\ge0$ and an integer precision $b\ge1$, compute

Then $m/2^b\le\sqrt{h}<(m+1)/2^b$, unless exact equality holds at the lower endpoint, which is checked by squaring integers. Multiplication by the signed rational coefficient and addition of the rational part give an enclosing rational interval for $a+b'\sqrt{h}$.

For two strictly ordered endpoints, refine their enclosures until the upper endpoint of the left enclosure is less than the lower endpoint of the right enclosure. Their rational midpoint is the desired sample. The enclosures shrink to distinct real numbers, so the process terminates. All comparisons certifying the selected point are exact. The same procedure gives horizontal and vertical samples.

Proof. The event count follows from pairwise circle and segment intersections and endpoint counts. Each slab has at most $2n+h=O(M)$ section ordinates, yielding the band count and sorting count. A band sample is checked against $O(h)$ triangles and $n$ contacts, giving the direct labeling bound. At most $O(M^2)$ distinct region labels are needed by Equation (8), and pairwise inclusion filtering of that many labels takes $O(M^4)$ mask comparisons. The claimed retained size is the canonical certificate bound, independent of how many times one region is sampled.

These are operation counts, not constant-bit-time claims. Integer sizes and the number of dyadic refinement steps matter. We do not claim an optimal arrangement algorithm or a new algebraic root-separation theorem. The important guarantee is finite exactness, with a small retained certificate and a rational witness for every retained mask.

Independent verification of a returned failure

A rejected query supplies $A$ and $q_A$. A checker can verify that $q_A\in T$, evaluate all rational squared distances to recover $S(q_A)=A$, and confirm $A\in F$. This independently verifies failure of the query without trusting the geometric sweep. Acceptance additionally requires completeness of the sample construction, which is supplied by Theorem 4.1; checking a few returned witnesses alone cannot prove completeness.

Deleting every contact in $A$ gives a concrete adversarial failure. For a domain cut, the returned location has the mapped active-domain set recorded in the certificate. For a virtual-contact bundle, the checker evaluates the finite conjunctions at that same point. The location is therefore linked to the actual model rather than to a missing cell in a plot.

A universal exact common-radius certificate

The fixed-radius antichain answers many failure rules at one geometry. This section fixes the sites and target and determines the exact common radius needed for any one of those rules. All sites share the same radius in this theorem. Unequal-radius targets are handled by Theorem 4.1, but the bisector proof below must not be applied unchanged to additive weighted distances.

Let $w:2^{[n]}\to\{0,1\}$ be monotone, with $w(\varnothing)=0$ and $w([n])=1$. Define

This is the smallest common radius for which the active contact set at $x$ wins. It is a finite minimum of finite maxima of distance functions, so it is continuous and 1-Lipschitz. The same maximum–minimum algebra underlies lattice-polynomial descriptions of reliability systems [21, 22].

Let $\mathcal{L}$ contain all nontrivial perpendicular bisectors of pairs of sites and the supporting lines of all target edges. Coincident sites give no bisector; coincident lines are stored once. Let $Q_T$ contain all target vertices and every intersection of two nonparallel lines in $\mathcal{L}$ that lies in $T$.

Proof. The perpendicular bisectors divide the plane into cells on which the weak ordering of distances to the sites is fixed. Identical sites remain tied everywhere; there is no need to break such a tie geometrically. The additional target-edge lines subdivide every target triangle into bounded convex polygons. On the interior of one such polygon, Theorem 5.1 selects one fixed distance group, so $\rho_w(x)$ equals $\lVert x-c_j\rVert$ for a fixed representative site $c_j$ in that group.

The norm function is convex. Every point of the polygon is a convex combination of its vertices, and its distance to $c_j$ is at most the corresponding convex combination of vertex distances. Thus the maximum on the polygon is attained at a vertex. By continuity of $\rho_w$, the formula obtained in its interior extends to its boundary even when new distance ties occur there. Every polygon vertex is either a target vertex or an intersection of two lines in $\mathcal{L}$, hence belongs to $Q_T$. Taking the maximum over the finitely many target polygons proves that $\max_T \rho_w=\max_{Q_T}\rho_w$.

Coverage at common radius $r$ is equivalent to $r\geq\rho_w(x)$ at every target point by definition, giving Equation (13). There are at most $\binom{n}{2}+h$ lines and a quadratic number of their pairwise intersections. Rational line coefficients give rational intersection coordinates. Squared distances at those points are rational, and Theorem 5.1 selects one of them. Their finite maximum is rational. A maximizing point fails at any smaller radius, proving the witness assertion. □

Remark 5.3 (Universality and complexity). The same $Q_T$ works for cardinality thresholds, weighted budgets, domain rules and any fixed monotone activation of primitive contacts. It does not say that the critical radius is the same for those rules. Its point is reusability and an exact threshold; specialised higher-order or coloured Voronoi methods can be faster for a single rule.

The support reduction in fixed dimension

The full line arrangement contains many vertices created by distance ties that are irrelevant to a given threshold. A local maximum argument removes them simultaneously for every monotone rule. We state the argument in $\mathbb{R}^d$ to make the supporting geometry explicit.

For a finite union of rational nondegenerate $d$-simplices, construct a set $Q^{\mathrm{supp}}$ as follows. Include every simplex vertex. For each $f$-dimensional face $G$ of each simplex, with $1\leq f\leq d$, and each choice of $f+1$ sites, solve the $f$ equations asserting equal squared distance to those sites, restricted to the affine hull of $G$. Retain the solution if it is unique and lies in $G$. All these equations are linear after subtracting one squared-distance equation from the others.

The set is independent of $w$, has rational coordinates, and for $t$ supplied simplices has size at most

In particular, for fixed dimension it has $O(t(1+n^{d+1}))$ points, and $(r_w^*)^2$ is rational.

Proof. Choose a maximizer $x$ of the continuous function $\rho_w$ on $T$. Choose one target simplex containing $x$, and let $G$ be its unique face whose relative interior contains $x$. Write $f=\dim G$. If $f=0$, $x$ is a supplied vertex and is already in the certificate.

Suppose $f\geq1$. Let $s=\rho_w(x)$, let $L$ contain the sites strictly closer than $s$, and let $J$ contain those at distance exactly $s$. By Theorem 5.1, $w(L)=0$ and $w(L\cup J)=1$. There is a neighbourhood of $x$ in which all sites of $L$ remain closer than all sites of $J$, and all other sites remain farther than all sites of $J$.

Fix $j_0\in J$. Consider the linear functionals $v\mapsto(c_j-c_{j_0})\cdot v$ on the $f$-dimensional tangent space of $G$. If they have rank less than $f$, choose a nonzero tangent vector $v$ annihilated by all of them. Along $x+uv$ all distances to sites in $J$ remain equal: their squared-distance differences are zero at $u=0$ and have zero linear coefficient. For sufficiently small positive and negative $u$, the order separation from $L$ and the farther sites persists, and $x+uv$ stays in $G$. The winning threshold is therefore the common distance to $J$.

Its square along this line is

Since $v\neq0$, at least one of two sufficiently small opposite nonzero values of $u$ makes this strictly larger than $s^2$. This contradicts maximality of $x$.

The functionals thus have rank $f$. Choose $f$ independent ones, corresponding to $f$ sites in $J$ together with $j_0$. Their equal-distance equations have a unique solution in the affine hull of $G$, namely $x$. This is one of the retained support points. Consequently a global maximizer lies in the certificate, proving Equation (14). The count enumerates the faces and site subsets; singular systems can only reduce it. Unique solutions of rational linear systems are rational, and Theorem 5.1 again makes the squared threshold rational. □

Proof. The $f=1$ systems are bisector–edge intersections; a bisector coinciding with an edge does not have full rank and contributes no isolated solution. The $f=2$ systems are the circumcenters of noncollinear triples. There are at most $\binom{n}{2}$ bisectors and $h$ edges, at most $\binom{n}{3}$ circumcenters and $O(h)$ supplied vertices. □

The full arrangement construction provides a second analytical construction of a valid support set. The support theorem gives the smaller main construction. Its proof treats arbitrary monotone rules, not only the $k$th-nearest distance.

Proof. For any downward-closed family $\mathcal{F}$, let $w$ be its complement. If $w([n]) = 0$, no contact set can win and both the target and the support set fail. Otherwise Theorem 5.4 says that winning at all support points at radius $r$ is equivalent to winning throughout $T$. The two collections of realized masks therefore have identical answers to every failure-family query. Their minimal antichains must coincide: if a true minimal pattern $A$ had no sampled pattern contained in it, the query $\mathcal{F} = 2^A$ would accept all samples and fail at $A$. Conversely every sampled mask is realized in $T$ and contains a true minimal pattern. This proves Equation (16). Composition with an activation map preserves monotonicity, giving the last assertion. □

Support witnesses can lie on the target boundary. The vertical algorithm instead supplies interior witnesses for the same minimal masks. Either is a valid rational target witness; their roles must not be confused with merely checking a finite grid chosen without a completeness theorem.

Exact line arithmetic

The bisector of $c_i$ and $c_j$ is

Represent a line by its rational coefficients $(a,b,c)$ in $ax+by+c=0$. Clearing denominators, dividing by the common integer divisor and choosing the first nonzero coefficient positive gives a canonical representation. For two lines $(a,b,c)$ and $(d,e,f)$ with determinant $\Delta=ae-db\ne0$, their intersection is

Every candidate membership test in a closed triangle is a rational orientation test. Every distance-prefix comparison uses rational squared distances. Consequently the radius computation uses no radical comparison; radicals appear only when displaying the final radius as $\sqrt{s}$.

A reusable engineering example

Take the four sites $(\pm1,\pm1)$ and target $[-3/5,3/5]^2$. Two-contact coverage requires squared radius $68/25$. Assigning both contacts in each column to the same failure domain requires squared radius $89/25$ to survive a domain loss. Assigning the two diagonals as the domains instead requires $68/25$. The saved rational worst points include $(-3/5,0)$ for column wiring and a target corner for diagonal wiring.

These values are derived directly in Section F. The separation is operational: a nominal radius $9/5$ lies between the two thresholds. At that radius, diagonal wiring meets the one-domain-loss requirement and column wiring fails, although ordinary two-contact coverage is identical in both designs.

Why unequal offsets require a different proof

If contact $i$ has radius $r_i+s$ with a common additive design variable $s$, the relevant scalar functions are $\lVert x-c_i\rVert-r_i$. Their equality loci are generally hyperbolas, not the perpendicular bisectors used here. A distance-order arrangement for the unweighted sites would then omit changes in the active ranking. The exact fixed-radius sweep still applies after the radii are chosen, and a general semialgebraic optimization approach is possible, but the rational threshold statement of this section does not cover that weighted problem.⁶

Common convex parts and exact resilience frontiers

The support argument does not depend on the distance functions themselves. What it uses is a common convex part and affine differences. This gives a more general analytical theorem and an exact two-parameter consequence for coverage design.

A support theorem for lattice selectors

Let $T$ be a finite union of nondegenerate $d$-simplices. Suppose $\psi$ is continuous and convex on every supplied simplex, and define

For a monotone rule $w$ with $w(\varnothing)=0$ and $w([n])=1$, set

This is a lattice polynomial without added constant arguments. Its value is one of the input values at every point. It commutes with a common additive shift of all those values. These elementary properties follow directly from the finite minimum and maximum operations.

Construct $Q_T(a,b)$ by including all target vertices and, on each $s$-dimensional simplex face, the unique solutions of $s$ independent equations

that lie in that face. The set depends on the affine data and target, but not on $w$ or $\psi$.

Proof. First suppose that $\psi$ is strictly convex on every nontrivial segment of every simplex. Let $x$ maximize $L_w(f)$ and lie in the relative interior of a target face $G$ of dimension $s$. If $s=0$, it is a supplied vertex. Otherwise let $J$ consist of the indices whose input value equals $L_w(f)(x)$, and let $I$ contain those with strictly smaller value. The prefix argument gives $w(I)=0$ and $w(I\cup J)=1$.

If the affine differences in Equation (19) for indices in $J$ do not span the dual tangent space of $G$, choose a nonzero tangent direction $v$ annihilated by them. Along a sufficiently short segment $x+uv$, the values for all indices in $J$ remain equal. By continuity, the smaller and larger input groups remain separated from this tied group. The selected value along that segment is therefore

It is strictly convex as a function of $u$. Its value at the middle of two distinct points is strictly smaller than their average, so at least one nearby endpoint has a greater value. Both endpoints remain in $G$, contradicting maximality. Thus $s$ independent differences occur, and $x$ is the unique solution of one of the listed systems.

For merely convex $\psi$, replace it by $\psi_\varepsilon(x)=\psi(x)+\varepsilon\lVert x\rVert^2$, with $\varepsilon>0$. The affine differences and hence $Q_T(a,b)$ do not change. Common-shift commutation gives

The strictly convex case applies. Since $T$ is compact, these functions converge uniformly to $L_w(f)$ as $\varepsilon\downarrow0$. Their maxima on $T$ and on its finite support set converge to the respective maxima, proving Equation (20).

The count and rationality follow by enumerating the faces and index sets, then solving rational linear systems exactly. No differentiability of $\psi$ is required. □

Remark 6.2 (The convexity boundary). The common-convex-part hypothesis is substantive. With one input $f_1(x)=-x^2$ on $[-1,1]$, the support construction contains only the endpoints, while the maximum is attained at zero. No statement for arbitrary shared nonconvex parts follows from Theorem 6.1.⁷

The theorem identifies a finite set of places at which any one of a large family of spatial logical requirements can be hardest to meet.

Power-controlled unequal footprints

Fix rational site weights $\omega_i$ and define

At a common power parameter $t\in\mathbb{R}$, contact $i$ is active when $p_i(x)\le t$. Its footprint is a disk of squared radius $t+\omega_i$ when this is nonnegative and is empty otherwise. A zero squared radius gives a point. The footprints may therefore have unequal radii.

Equation (21) has common convex part $\lVert x\rVert^2$, affine coefficient $-2c_i$ and constant $\lVert c_i\rVert^2-\omega_i$. Its tie hyperplanes are the standard radical or power bisectors [26]. The underlying power-diagram geometry is established; the theorem here uses all required support systems for simultaneous monotone-rule certification.⁸

Proof. At a target point, the least power parameter for which the active prefix wins is the inner minimum–maximum. Apply Theorem 6.1. The input power values at rational support points are rational, and the finite selector and maximum retain rationality. The lower-bound constraint and the witness assertion follow immediately. □

The equal-radius theorem is recovered by taking every $\omega_i=0$ and $t=r^2$. A common positive-definite rational quadratic form also fits: replacing the squared norm by $(x-c_i)^{T}A(x-c_i)$ gives a common convex part $x^{T}Ax$ and affine differences. Thus the same argument covers a common anisotropic ellipsoidal metric. Semidefinite $A$ is allowed by Theorem 6.1, although its sublevel sets may be unbounded before intersection with the compact target.

A finite exact radius–budget frontier

For each power parameter $t$, let $S_t(q)=\{i:p_i(q)\le t\}$. The same support set has the antichain identity

The proof of Theorem 5.6 applies with Theorem 6.1: if a true minimal pattern were absent from the sampled lower closure, the failure query $2^A$ would contradict the universal maximum identity.

For nonnegative deletion costs, define

This is the minimum deletion cost that destroys full target coverage at parameter $t$.

Proof. For each support point, the summands in Equation (24) enter at their exact power levels and stay present. Its cost function is a finite nondecreasing right-continuous step function. A finite minimum of such functions is again nondecreasing and right-continuous, with no additional breakpoints. At fixed $t$, the minimum is over finitely many linear forms in $c$, proving concavity and homogeneity. The budget and witness conclusions are Theorem 3.7 combined with Equation (23). □

There are at most $n|Q_T^\omega|$ event levels before removing duplicates. Coincident levels are inserted together; closed footprints accept equality. The number of actual jumps may be much smaller. The frontier is exact and finite; optimising the positions themselves is a different problem.

Exact verification of every selected subnetwork

Let $U\subseteq[n]$ be the contacts retained by a design, and let $w_0$ specify the required residual service. The rule

is monotone. If it never wins, the design is infeasible. Otherwise the same support theorem gives its exact coverage threshold. In particular, the canonical support set is valid for every one of the $2^n$ subnetworks without being constructed anew for each.

For $k$-coverage at a fixed power parameter, binary selection variables $z_i$ satisfy the complete target constraints

Any proposed design can be checked by these inequalities. They turn continuous target feasibility into a finite exact system but leave the combinatorial design optimization intact. A minimum-cost selection problem is still an integer program; its difficulty is not removed by the geometric theorem.

The distinction between geometry and decision variables is useful. The support set and power values can be checked once. Changing costs, failure rules, domain assignments or selected contacts then changes only the finite logical and optimization layer. The proofs above establish this separation analytically.

Exact robustification under product geometric uncertainty

The usual margin bound gives sufficient protection against geometric errors. In a product uncertainty model one can do better: the robust coverage region has an exact reduction. This is a worst-case statement about possible placements, with no probability distribution assumed.

Let contact $i$ have a family of possible closed footprints $D_i(\theta_i)$ indexed by a nonempty set $\Theta_i$. The complete uncertainty set is

Define the footprint guaranteed for every local parameter by

The fault rule $w$ is fixed on the contact labels and does not depend on the realized parameters.

Proof. Write $I(x)=\{i:x\in E_i\}$. Every active set $S_\theta(x)$ contains $I(x)$, so a winning $I(x)$ gives the left side by monotonicity. Conversely, if $i\notin I(x)$, choose one local parameter $\theta_i$ for which $x\notin D_i(\theta_i)$. Choose arbitrary parameters for the other contacts. The product hypothesis permits all those local choices simultaneously. Their resulting active set is exactly $I(x)$. Thus the left side requires that this set wins. This proves Equation (27). Finally, universal quantifiers over the target point and the parameter realization commute, giving Equation (28).

The proof is a statement about an attainable least active set. It is not an unjustified exchange of an intersection and a union. Compactness and convexity are unnecessary for the logical theorem, although they are useful for computing the guaranteed footprints.⁹

Independent displacement balls and radius intervals

Suppose the center of contact $i$ is $c_i+u_i$, with $\lVert u_i\rVert\le\epsilon_i$, and its radius lies in an interval $[\underline{r_i},\overline{r_i}]$ with $\underline{r_i}\ge0$. Parameters for distinct contacts may be chosen independently. The largest distance from $x$ to a possible center is

The upper bound is the triangle inequality. Equality follows by taking the displacement directly away from $x$, or any direction when $x=c_i$.

Corollary 7.2 (Exact erosion). The guaranteed footprint is the closed disk of radius $\underline{r_i}-\epsilon_i$ centered at $c_i$ when this radius is nonnegative, and is empty otherwise. Coverage of the eroded family is necessary and sufficient for robust full-target coverage under every fixed monotone failure rule.

Proof. Membership in $E_i$ is exactly the inequality $\lVert x-c_i\rVert+\epsilon_i\le\underline{r_i}$. Apply Theorem 7.1.

When $\underline{r_i}=\epsilon_i$, the footprint is a point rather than an empty set. The algorithm preserves the distinction, although isolated footprint points cannot rescue a positive-area target that fails on an open subset. An empty guaranteed footprint is represented by an always-inactive contact, not by a disk with a negative radius.

Corollary 7.3 (Exact common-radius uncertainty allowance). If all nominal radii equal $r_0$, all downward radius errors are at most $\eta$ and all independent displacement balls have radius $\epsilon$, with $r_0\ge\eta$, robust coverage holds exactly when

If $r_0-\eta\ge r_w^*$, the maximum allowed independent displacement radius is $r_0-\eta-r_w^*$. The threshold $r_w^*$ is supplied by Theorem 5.2.

Independent polygonal displacement uncertainty

Suppose $u_i$ ranges over the convex hull of a finite rational set $V_i$. For fixed $x$ and any convex combination $u=\sum_v\lambda_vv$,

The reverse inequality for the supremum holds because the vertices themselves are allowed. Therefore

Theorem 7.4 (Finite primitive-disk reduction). For product polygonal displacement uncertainty, introduce one primitive disk for every shifted center in Equation (29). A physical contact is active exactly when every primitive disk in its bundle is active. Applying that monotone bundle map to the primitive target antichain gives an exact robust target certificate for every failure family on the physical contacts. If the lower radii are common, the same bundle map can be used in the exact common-radius theorem.

Proof. Equation (29) proves the bundle activation statement. Theorem 3.6 gives its target antichain, and Theorem 7.1 identifies the robust region. With common radii, the winning predicate on primitive sets is the composition of the monotone physical rule and the monotone bundle map. It meets the hypotheses of Theorem 5.2 when the full primitive set wins.

There are $N=\sum_i\lvert V_i\rvert$ primitive disks. The target certificate-size bound uses $N$ in place of the number of physical contacts. This is an exact vertex reduction of the stated uncertainty polytope, not an approximation of a displacement ball by a polygon. For independent boxes, four corner disks per physical contact suffice in the plane.

Proof. The guaranteed footprints are finite intersections of disks. Every realized primitive mask is contained in a maximal primitive nerve face. Monotonicity of the bundle map sends this containment to containment of physical masks. Every maximal primitive face is realized at a point, so its image is also realized. Taking maximal images therefore gives exactly the maximal physical masks. Each physical nerve face is contained in one of these maximal masks. Apply Theorems 10.2 and 11.2.

For arbitrary monotone activation using disjunctions, target relabeling remains correct, but the resulting physical footprints need not be convex. The classical convex nerve equivalence then requires separate good-cover hypotheses. The target certificate does not silently inherit that extra topological assertion.

A counterexample for shared placement errors

The product hypothesis cannot be dropped. Put nominal centers at $(\pm3/5, 0)$, give both disks radius $1$ and let them share one displacement vector $u$ with $\lVert u\rVert\le3/5$. At the origin,

Every point of the square $[-1/10,1/10]^2$ is within $\sqrt{2}/10$ of the origin, so its distance to at least one shifted center is at most

The shared-error model therefore covers the whole square for every $u$. Eroding each nominal disk independently by $3/5$ gives radius $2/5$ and leaves the origin uncovered. That eroded test is sufficient but is not necessary for this shared-error support. Under genuinely independent errors, choosing opposite outward shifts would uncover the origin, exactly as Theorem 7.1 predicts.

Fault-domain correlation and geometric correlation are different inputs. The failure family may correlate contact losses arbitrarily in Theorem 7.1; the theorem restricts the support of the geometric parameters. Statistical independence is not a substitute for stating that support. These distinctions are central to applying robust optimization correctly [23].

The resilience polyhedron and certified protection design

The target antichain converts a continuum of spatial failure opportunities into a finite family of cuts. We now use that family to design a protection allocation. The cost model is explicit: allocating a nonnegative value $c_i$ makes deletion of contact $i$ cost $c_i$ to the adversary, and providing that protection consumes $d_i c_i$ units of resource, where $d_i>0$.¹⁰

Concavity and weakest-point certificates

Equation (10) shows that $\kappa_T$ is a finite minimum of linear forms. It is concave, positively homogeneous and coordinatewise nondecreasing on $\mathbb{R}_{\ge0}^n$. A minimizing cut $A$ supplies both an attack and a supergradient:

Indeed, the right side is $c'(A)$, one of the values over which $\kappa_T(c')$ takes its minimum. At a tie, any convex combination of the tied cut vectors is also a supergradient. The geometric witness associated with the chosen cut identifies where that adversarial value is attained.

Define the fractional blocking polyhedron

For $\tau>0$, the condition $\kappa_T(c) \ge\tau$ is equivalent to $c/\tau\in\mathcal{B}_T$. This is the standard fractional transversal formulation of a cut hypergraph, here with exact geometric witnesses on the constraints.

Primal and dual protection programs

For a total protection budget $C \ge0$, the best guaranteed deletion cost is

The number of cut constraints is bounded quadratically in the geometric input size. This does not make all sensor-placement or wiring problems linear programs: positions and domain assignments remain separate variables in different models.

The finite minimax lemma proved in Section E exchanges this maximum and minimum after the adversary randomizes over cuts. The inner maximum over $x$ is the largest coordinate $\sum_{A\ni i}\lambda_A/d_i$, giving Equation (33). For $C=0$, both sides are zero. The feasible sets are compact after normalization, so optima are attained. □

The dual vector is a distribution over weakest target patterns, not a model of the actual failure distribution. Its purpose is to prove that no allocation under the stated resource budget can exceed the certified value. The coordinates $\lambda_A$ can be rational when the input is rational, and equality in Equation (35) is then checkable by integer arithmetic.

Duplicating contacts and a sharp budget distinction

Suppose each original contact $i$ is replaced by $b_i\ge1$ independently labeled copies with exactly the same footprint. Each target cut is expanded by replacing $i$ with all its copies. Under unit deletion costs this can increase the number of required deletions substantially. Under a fixed linear protection budget it has a different effect.

Proof. Given copy allocations $c_{i,j}$, put $\bar{c}_i = \sum_j c_{i,j}$. Every expanded cut has cost $\sum_{i \in A} \bar{c}_i$, and the budget is $\sum_i d_i\bar{c}_i$. Thus every copy allocation has exactly the value of a feasible original allocation. Conversely every original allocation is realized by putting its entire $c_i$ on one copy and zero on the remaining copies. Both optimization problems have the same feasible aggregate values.

The four-corner panel and its duplicated eight-contact version illustrate the distinction. Their minimum numbers of individual deletions are two and four, respectively, but their unit-budget optimal protection values are both $1/2$. Independent Bernoulli reliability can still improve after duplication. A design comparison must specify which of these objectives is being optimized.

Numerical proposals and rational verification

A candidate allocation and dual multipliers may come from any source, for instance a floating-point linear program. Round them to rationals, enforce nonnegativity and budget feasibility, normalise the dual distribution, and set $\mu$ to the largest exact ratio in Equation (34). Both bounds of Equation (35) are then rational.

Only exact equality establishes verified optimality. If rational recovery yields a gap, the valid conclusion is the interval in Equation (35). The allocations in the analytical examples below are derived symbolically with matching dual bounds.

Fault-domain synthesis and probabilistic reliability

The same geometric certificate supports two different questions: whether every allowed failure is tolerated, and how often a target remains covered under a specified probability law. The first is adversarial and distribution-free. The second requires an actual distribution. Their numerical answers need not agree.

Wiring as a hypergraph coloring problem

Assign contact $i$ to a domain $g(i) \in\{1,\ldots,s\}$. A loss of a domain deletes all contacts assigned to it. For $A \in\mathcal{A}_T$, write $g(A) = \{g(i) : i \in A\}$.

Proof. Apply Theorem 3.6 to the domain map. A domain contact set survives every loss of $q$ domains exactly when it has at least $q+1$ members, as in Theorem 2.5. Theorem 3.3 gives the equivalence and its failure witness.

For $q = 1$, the cut hypergraph must have no monochromatic edge. When all critical cuts have size two, this is ordinary proper graph coloring. Requiring every cut to contain every one of a specified set of colors is the familiar polychromatic or cover-decomposition formulation [20]. Equation (36) allows more domains than the number of required surviving alternatives.

The finite constraints can be written as an integer program. Let $z_{ig}$ indicate assignment of contact $i$ to group $g$, and let $u_{Ag}$ indicate whether group $g$ occurs in cut $A$. Require

with binary variables. The middle two constraints enforce the exact logical disjunction. Any proposed assignment can be checked directly against every certified cut. Proving that fewer groups are impossible requires a separate lower bound or exhaustive proof.

Ordinary target-coverage reliability

Let $F$ now be a random failed-contact set. For ordinary coverage after that failure,

The analogous formula for domain failures uses the mapped domain antichain. This is the standard minimal-cut representation of a semicoherent reliability system [19].

Some contacts may be irrelevant to the target; relevance of every component is not assumed.

If contacts fail independently with probabilities $p_i$, direct state enumeration gives

For cuts $A_1,\ldots,A_m$, inclusion–exclusion also gives

The empty $J$ contributes one. Both formulas are exact and generally exponential; the geometric size bound does not turn arbitrary reliability evaluation into a polynomial-time algorithm.¹¹

For the odd-cycle example with identical independent failure probability $p$,

The first equality enumerates the four mutually exclusive successful states, and its polynomial expansion gives the second equality directly.

The same four sensors with two wiring choices

For the four-corner panel, column wiring gives domain cuts $\{1\}$ and $\{2\}$: both domains must work. Diagonal wiring gives the single domain cut $\{1,2\}$: at least one domain must work. Under independent identical domain failure probability $p$,

At $p=1/10$ these are $81/100$ and $99/100$. The independent-failure law is a chosen model for this comparison. If the two domain failures are arbitrarily dependent but keep the same marginals $p$, the sharp two-event bounds are

They follow by writing the joint failure probability $a$ between $\max(0,2p-1)$ and $p$. Column success is $1-2p+a$, while diagonal success is $1-a$. At $p=1/10$, the intervals are $[4/5,9/10]$ and $[9/10,1]$.

The diagonal success event contains the column success event for every fixed domain-failure state. Thus its dominance under the same joint distribution does not require independence, even though the numerical values in Equation (40) do.

Marginal-only reliability as a finite probability program

If only marginal probabilities and selected dependence constraints are known, introduce a probability $\pi_F$ for each failure state. The sharp lower and upper coverage probabilities solve

subject to $\pi_F\ge0$, $\sum_F\pi_F=1$, $\sum_{F\ni i}\pi_F=p_i$ and any stated additional linear probability constraints. This is the logical probability formulation of Hailperin [24], applied to the exact geometric cut list. It can have $2^n$ variables. No efficient solution for every dependence model is claimed.

Maintaining a stronger residual requirement

Equations (10) and (37) concern ordinary coverage after a failure. If the desired residual rule is a different monotone predicate $w_0$, the exact condition is instead

For nonnegative deletion costs, the exact attack cost becomes

If some $A$ already loses under $w_0$, the inner minimum includes $B=\varnothing$ and the value is zero. Otherwise, a failure of an actual active set also fails a contained minimal active set, giving a no-more-expensive cut in that set; conversely that minimal set is realized at its witness. This proves Equation (43).

For residual $k$-coverage at a pattern of size $a\ge k$, delete its $a-k+1$ cheapest contacts. A general $w_0$ may require a difficult inner optimization, and its complete minimal attack family can be much larger than $\mathcal{A}_T$. The universal geometric reduction remains exact without implying that every logical optimization is easy.

The facet-intersection model

Let $N$ be the nerve of a finite family of nonempty compact convex sets. Every face lies in a maximal face. Empty footprints can be removed beforehand without changing any pointwise active set on the remaining labels. Keep the failure rule restricted to those labels.

Definition 10.1. The winning-face complex $\Gamma_F(N)$ has one vertex for each $\sigma\in\mathcal{P}_F$. A nonempty collection $\mathcal{A}$ of its vertices is a simplex if

With $\mathcal{M}=\operatorname{Max} N$, the facet-intersection complex has nonempty faces

Upward closure of winning sets implies that Equation (45) is closed under taking nonempty subsets of $A$: removing a maximal face makes the intersection larger. Thus it does define an abstract simplicial complex. In contrast, enlarging a contact set in $N$ need not preserve being a face, so the directions of the union and intersection tests must not be reversed.

The combinatorial equivalence is an instance of Dowker duality [6, 7] for the containment relation between winning faces and maximal nerve faces. It does not require a bound on the sizes of those faces.

Proof. By Theorem 2.2, the sets $D_{\sigma}$, indexed by $\sigma\in\mathcal{P}_{\mathcal{F}}$, cover $R_{\mathcal{F}}$. A finite intersection of these sets is

It is nonempty exactly when Equation (44) holds, and when nonempty it is compact and convex. The finite closed-convex nerve theorem therefore identifies its nerve $\Gamma_{\mathcal{F}}(N)$ with $R_{\mathcal{F}}$ up to homotopy. The closed-convex hypothesis is used here; an arbitrary cover by closed contractible sets would not justify the same argument [8].

For completeness, we prove the combinatorial equivalence by explicit maps. Let $Q_{\Gamma}$ and $Q_{\mathcal{C}}$ be the nonempty face posets of $\Gamma_{\mathcal{F}}(N)$ and $\mathcal{C}_{\mathcal{F}}(N)$. Set

For a face $A$, its union is in $N$, so $f(A)$ is nonempty. The intersection of all members of $f(A)$ contains that union, which contains a winning face. Hence $f(A)$ is a face of $\mathcal{C}_{\mathcal{F}}$. For a face $B$, its intersection $I_B$ is a winning face of $N$. In particular, $I_B\in g(B)$, and the union of all members of $g(B)$ is exactly $I_B$. Thus $g(B)$ is a nonempty face of $\Gamma_{\mathcal{F}}$.

Both maps reverse inclusion. Their composites preserve inclusion and satisfy

For the first inclusion, each $\sigma\in A$ lies in every maximal face containing the union of $A$. For the second, $\bigcup g(B)=I_B$ lies in every $M\in B$.

An order-preserving map pointwise above the identity induces a map homotopic to the identity on the order complex; a proof by prisms is given in Section A. An order-reversing map also induces a simplicial map on order complexes, by reversing the order of each image chain. Applying this observation to Equation (49), the realizations of $f$ and $g$ are mutually inverse up to homotopy. The order complexes are the barycentric subdivisions of $\Gamma_F$ and $C_F$, whose realizations are homeomorphic to those of the original complexes.

If there is no winning nerve face, all three spaces are empty by definition and the assertion is immediate. □

Proof. The subfamily $(D_\sigma)_{\sigma\in\Lambda_F}$ is still a finite convex cover of $R_F$ by Equation (4). Its nerve is the stated union complex. Apply the same closed-convex nerve theorem and Theorem 10.2. □

Using every winning face in $\Gamma_F$ is convenient for naturality but unnecessary in computation. Using only minimal winners is often still expensive. The dual complex evaluates the predicate only on intersections of maximal nerve faces and does not list either collection of coalitions.

Remark 10.5 (Changing geometry). Maximal nerve faces can change when radii or positions change. The literal vertex sets of the corresponding facet-intersection complexes then need not be nested. Theorem 10.4 fixes the geometry; it does not assert a raw simplicial inclusion for moving radii. Geometric perturbation inclusions are proved in Section 12, and standard multicover bifiltrations already address simultaneous radius and multiplicity parameters [4, 5].

Proof. The chain groups and boundary maps relevant to degrees zero and one are

Higher-dimensional simplices do not change these maps. In the graph of $K$, the incidence matrix has rank $V-c$: a spanning tree gives rank $v-1$ on a connected component with $v$ vertices, and every additional edge has boundary equal to the sum of boundaries along its tree path. Thus $\dim\ker\partial_1=E-V+c$. Quotient by $\operatorname{im}\partial_2$ to obtain Equation (50).

Exact geometry without nerve-face enumeration

The duality theorem is useful only if the maximal nerve faces can be obtained reliably. For disks, a finite arrangement construction avoids listing every intersecting subfamily. In this section

and coincident disks keep their distinct contact labels.

Proof. Every witness label is a nerve face, because the witness itself lies in all its labeled disks. Let $\sigma$ be a maximal nerve face and set $K=\bigcap_{i\in\sigma}D_i$. This is nonempty and compact. Choose a point $x\in K$ with minimal first coordinate.

If $\sigma$ contains a zero-radius disk, then $K$ consists of its center, which is a listed witness. Suppose all its disks have positive radius. At least one constraint is active at $x$: if all were strict, a small open neighborhood of $x$ would lie in $K$, contradicting minimality. If two active constraints have distinct supporting circles, $x$ is one of their boundary intersections and is listed.

The remaining case has only one distinct active supporting circle, possibly repeated with several labels. Every other disk of $\sigma$ contains a neighborhood of $x$. In a sufficiently small neighborhood the only effective constraint is therefore the closed disk bounded by that active circle. Unless $x$ is its leftmost point, there are points of that disk arbitrarily close to $x$ with smaller first coordinate. They still satisfy every locally slack constraint, a contradiction. Thus $x$ is the leftmost point of an active disk and is listed.

In all cases $\sigma\subseteq L(x)$. The label is a nerve face and $\sigma$ is maximal, so equality follows. Taking maximal labels removes only proper subfaces and duplicates. Each noncoincident pair of circles has at most two intersection points, which proves Equation (51).

Remark 11.3. The extremal-point argument is an elementary disk-arrangement method. The bound concerns the number of maximal nerve faces, not the number of all nerve faces or all simplices of the dual complex. A single maximal face on $n$ labels contains $2^n-1$ nonempty nerve faces. Likewise $n^2$ dual vertices alone do not give a quadratic bound on all dual simplices.

Circle intersections in a quadratic extension

The witness labels can be determined without evaluating square roots approximately. Suppose $c_i\ne c_j$ and put

If $h<0$, the boundaries do not meet. If $h=0$, they meet at $B$. If $h>0$, their intersections are

Indeed, subtracting the two circle equations gives the line $(x-c_i)\cdot d=\alpha s$. Substituting $x=B+tP$ in the first equation gives $t^2=h$. This also covers internal and external tangency.

For a third disk, write $z=B-c_k$. Membership of $x_{\pm}$ is the inequality

When input numbers are rational, $A,C,h$ are rational. No coordinates of a square-root point need be rounded.

Proof. The first three cases follow from signs. In the fourth case the desired inequality is $A\le(-C)\sqrt{h}$, with both sides nonnegative, so squaring preserves its direction and equivalence. In the fifth case it is $C\sqrt{h}\le-A$, again with nonnegative sides. These cases exhaust all possibilities. Equality is retained because the disks are closed.

Enumeration and chain construction

Algorithm 11.5 (Exact facet computation).

1. Interpret the finite coordinates and radii as rationals; reject negative radii or nonfinite input.

2. Label the $n$ leftmost points by squared-distance comparisons.

3. For each pair of distinct centers, compute Equation (52). If $h\ge0$, label its one or two boundary intersections using Theorem 11.4. Pairs with equal centers require no boundary computation.

4. Delete empty labels and duplicates. Sort the remaining masks by decreasing cardinality, and retain a mask exactly when it is not contained in a previously retained mask.

The output is $\operatorname{Max}N$ by Theorem 11.2.

With $m=|\mathcal{M}|$ and a winning predicate $w$, the full dual two-skeleton is constructed as follows. Retain $M\in\mathcal{M}$ as a vertex if $w(M)$ is true. An edge $\{M_i,M_j\}$ is retained if $w(M_i\cap M_j)$ is true. A candidate triangle is retained if all three edges exist and $w(M_i\cap M_j\cap M_k)$ is true. The edge checks are redundant mathematically for an upward-closed rule, but they avoid unnecessary work and ensure a consistent boundary indexing.

Each triangle gives a boundary column with three nonzero edge entries over $\mathbb{F}_2$. Gaussian elimination determines its rank, while a union–find structure computes the graph components. Equation (50) then gives both Betti numbers.

Proof. There are at most $n^2$ witnesses and $n$ membership tests per witness. A quadratic comparison of at most $n^2$ labels bounds the naive filtering step. Correctness of those steps follows from Theorems 11.2 and 11.4. The simplex count follows from $m\le n^2$, and every simplex through dimension two is included by its defining predicate. Theorems 10.2 and 10.6 identify the resulting homology with that of the surviving region. □

This is an arithmetic-operation and oracle-query bound. It is not a unit-time bit-complexity bound: rational numerator sizes, arbitrary-precision mask operations, predicate costs and elimination all matter. The worst-case number of dual triangles is $O(n^6)$, and the full dual complex may have exponentially many simplices. For $H_j$ with fixed $j$, its full $(j+1)$-skeleton suffices, giving at most $O(n^{2j+4})$ simplex tests by the same argument. Much finer multicover bifiltration algorithms are given in [4, 5].

Equal-radius verification by a different geometric formula

For equal-radius disks there is another exact intersection criterion, expressed through minimum enclosing circles of center triples. If $a,b,c$ are three centers, let

The squared minimum enclosing radius is

The first case includes right, obtuse, collinear and coincident configurations. The second is the circumradius formula for an acute triangle; its denominator is nonzero. Two equal-radius disks meet if their center distance squared is at most $4r^2$, and three meet if and only if $\rho^2\le r^2$. Planar Helly’s theorem extends the triple criterion to every larger subfamily.

Equation (55) supplies a separate analytical criterion for testing a proposed facet and its one-contact extensions. Completeness of the witness list is supplied by Theorem 11.2; checking triples alone would not, for an arbitrary list of purported facets, prove that completeness.

Continuous target certificates and perturbation control

A homotopy model describes the surviving region once the footprints are known. An engineering target is additional data: a compact set $T$ for which one wants $T \subseteq\mathcal{R}_F$. This section gives a sufficient test for that inclusion, with the same winning rule as the dual complex. The constant in the triangle bound is the familiar planar covering constant used in the companion coverage archive [2]; the extension here is its formulation for a general monotone failure predicate.

The winning margin

Assume that $\mathcal{W}$ is nonempty and define the contact slack functions

The winning margin is

Minimal winning sets in this formula range over the full contact label set; they need not have a nonempty footprint intersection. The formula describes a real-valued function even outside the covered region. If $\mathcal{W}$ is empty, $\mathcal{R}_F$ is empty and target certification is handled separately.

For ordinary $k$-fold coverage, $\phi_F$ is the $k$th largest slack. For a failure budget, sort the slacks in decreasing order and accumulate failure costs until their sum first exceeds $B$; the corresponding slack is the margin. Ties can be processed as a block, and zero-cost contacts do not change the threshold. For $q$ domain losses, first maximize the slack within each domain and then take the $(q+1)$st largest domain slack. These are ways of evaluating the same finite maximum–minimum formula, not assumptions of statistical independence.

A sharp triangle sampling bound

The winning coalition is allowed to differ between vertices and triangles. The argument only needs a winning coalition at the selected nearest vertex with enough margin to reach the point. It does not assume that one fixed coalition covers an entire target. For an equilateral triangle with one disk of radius $b < D/\sqrt{3}$ centered at each vertex, the center is uncovered although each vertex has ordinary one-fold margin $b$. Hence a smaller universal vertex-margin constant cannot replace $1/\sqrt{3}$ in this form of certificate.

Proof. By Equation (57), the desired test is winning of the set with $r_i-\lVert v-c_i\rVert\ge\sqrt{h}$. This requires $r_i\ge\sqrt{h}$, equivalent to the first inequality because $r_i\ge0$. Subject to it, both sides of $\lVert v-c_i\rVert\le r_i-\sqrt{h}$ are nonnegative. Squaring is therefore reversible and gives the second inequality of Equation (61). All coefficients outside $\sqrt{h}$ are rational, so Theorem 11.4 applies.

The test Equation (61) includes zero-diameter triangles and zero-radius contacts, and it needs only the three eligible contact masks and the exact squared diameter; no homology computation enters.

Uncertain geometry

Suppose the actual parameters satisfy

and put $\delta=\max_i(\epsilon_i+\eta_i)$. Write $\phi$ and $\phi'$ for the two winning margins with the same failure family.

Proof. For every $i$,

Finite minima and maxima preserve this uniform bound, proving Equation (62). If $\phi(x)\ge\delta$, then $\phi'(x)\ge0$. If $\phi'(x)\ge0$, then $\phi(x)\ge-\delta$. This proves the inclusions. For a target point choose its nearby triangle vertex and apply both the geometric Lipschitz bound and the parameter error bound.

For each offset $t$ the same argument gives $\{\phi\ge t+\delta\}\subseteq\{\phi'\ge t\}\subseteq\{\phi\ge t-\delta\}$. Thus the superlevel homology modules are $\delta$-interleaved, with the superlevel parameter ordered in the usual reverse direction. This statement concerns the geometric modules; no unproved nesting of changing maximal-facet vertex sets is required.

Proof. The inclusion-induced map on the right factors through $H_j(R_F(D'))$ by Equation (63). The rank of a factorization cannot exceed the dimension of its middle vector space.

The lower bound does not rule out extra classes born and killed inside the uncertainty interval. Equal endpoint Betti numbers, or even an isomorphism between endpoints, need not give the exact Betti number of every intermediate geometry. For a target failure certificate, on the other hand, a point $x\in T$ with $\phi(x)<-\delta$ remains uncovered for every admissible actual geometry by Equation (62). These are distinct conclusions and require distinct data.

Analytical design examples

All thresholds, probabilities and optimisation values in this section are derived below or in Section F.

Three assets and an obstruction to two-domain protection

Place contacts at $(-1,0)$, $(1,0)$ and $(0,3/2)$ with common radius $6/5$. Around the three pairwise midpoints $(0,0)$, $(-1/2,3/4)$ and $(1/2,3/4)$, take triangular target patches with offsets

Each patch lies in exactly its intended pair of disks; the complete inequalities are given in Section F. Thus

Two contacts always cover every target point, but two domains cannot protect all three patches against a domain loss. If the first two contacts have different colors, the third must differ from both to avoid a monochromatic pair. Three domains are necessary and sufficient.

This elementary odd-cycle argument distinguishes overlap count from a decomposition into independently surviving layers.¹²

Under unit total protection resource and unit protection coefficients, the cut cost is

If the full resource is used, this equals $1-\max_i c_i\le2/3$. Equality holds at $c_i=1/3$. Equivalently, a uniform dual distribution on the three cuts gives $\mu=2/3$, proving the exact optimality value through Theorem 8.1. For independent contact failure probability $p$, the target survives precisely when at most one contact fails, giving $1-3p^2+2p^3$.

A square target with four corner contacts

Take target $[-a,a]^2$ with $a=3/5$, sites $(\pm1,\pm1)$ and nominal radius $9/5$. Label them in order as $(-1,-1)$, $(-1,1)$, $(1,-1)$ and $(1,1)$. The critical patterns are

To verify completeness, write $u=\max(|x|,|y|)$ and $v=\min(|x|,|y|)$. The second-nearest squared distance is

This convex quadratic has maximum $2+2a^2=68/25$ at a vertex of the parameter triangle. The two nearest corners share a side; at a tie the active set contains one of those adjacent pairs. Since $81/25>68/25$, every active set contains a listed pair.

The point $(-11/20,0)$ has squared distances $481/400$ to the left corners and $1361/400$ to the right corners. Since $(9/5)^2=1296/400$, its active set is exactly $\{1,2\}$. The three symmetric points realize the other pairs. This proves Equation (64) without an enumeration procedure.

An exact power–resilience staircase

For the same geometry, let $t=r^2$ and assign unit deletion costs. The maxima of the first through fourth ordered squared distances are

The formulas for all four distances and their maxima are derived in Section F. Therefore the complete deletion-cost frontier is

Closed disks accept every left endpoint. For tolerance of $q$ arbitrary unit-cost deletions, the required frontier height is at least $q+1$. A request to tolerate two losses thus requires $t\ge89/25$, whereas nominal $t=81/25$ tolerates only one.

The resource optimum and the role of duplication

Each contact occurs in exactly two of the four critical pairs. Under $\sum_i c_i\le1$,

At least one pair therefore has cost at most $1/2$. Uniform allocation $c_i=1/4$ gives cost $1/2$ for every pair. It is optimal, and the uniform distribution on the four cuts is a dual certificate.

Two coincident copies at every corner raise the minimum number of individual unit-cost deletions from two to four. Yet under fixed linear protection budget, the optimal value stays $1/2$ by Theorem 8.3. No contradiction arises: the unweighted count assumes one cost per copy, whereas the protection problem optimizes total allocated cost under a fixed resource constraint.

Adding a fifth contact at the origin with the same radius $9/5$ gives another distinction. Its disk alone covers the target because $x^2+y^2\le18/25<81/25$. Allocate the full protection budget to that contact to obtain guaranteed deletion cost one. No cut can cost more than the total allocation one, so this is optimal. The bound follows analytically without identifying every new target cut.

Wiring and reliability

Assign the columns to two domains. The left-pair witness depends only on the left domain, and the right-pair witness depends only on the right domain. Both must remain functioning for full target coverage. Assigning the diagonals instead puts one member of every critical pair in each domain, so either domain alone covers the target.

Thus one-domain-loss tolerance fails for column wiring and holds for diagonal wiring. Under independent domain failure probability $p$, reliability is $(1-p)^2$ and $1-p^2$, respectively. The values at $p=1/10$ are $81/100$ and $99/100$.

The exact squared sensing thresholds are 89/25 for column wiring and 68/25 for diagonal wiring. Their symbolic derivation in Section F also gives the worst target locations. The nominal 81/25 lies strictly between them, so the wiring difference changes the accepted design without moving or adding a sensor.

Exact uncertainty allowances

Independent center errors in Euclidean balls of radius $\epsilon$ erode the effective radius to $9/5-\epsilon$ by Theorem 7.2. Two-contact target coverage is therefore robust exactly when

For independent displacement boxes of halfwidth 1/10, the exact critical squared radius is 157/50, derived in Section F. Since 157/50 < 81/25, the nominal design meets that box-error requirement. The box formula and ball formula are different exact uncertainty supports, not interchangeable numerical tolerances.

A three-dimensional sharpness example

Let the four sites be the vertices

of a regular tetrahedron, and let the target be its convex hull. Each site has squared norm three and their centroid is zero. If $x = \sum_i \lambda_i c_i$ is a convex combination of the vertices, then

At least one vertex distance squared is therefore at most $3-\lVert x\rVert^2$. Away from zero this is strictly less than three. At zero all four distances equal $\sqrt{3}$. Thus ordinary one-contact coverage has exact radius $\sqrt{3}$ and its unique worst location is the interior point zero.

All four sites tie there with rank three. No pair or triple of these vertices alone determines the unique three-dimensional equal-distance location. The example shows why the general support theorem allows $d+1$ sites on a $d$-dimensional target. More generally, the same variance identity applies to a cospherical simplex whose center lies in its interior.¹³

Order maps and the comparison homotopies

We spell out the finite order argument used in Theorem 10.2. For a poset $P$, its order complex has vertices $p \in P$ and simplices the nonempty chains. An order-preserving map sends chains to chains, possibly with repetitions; deleting repetitions gives a simplicial map. An order-reversing map does the same after reversing the order of the image chain. The order complexes of a poset and its opposite are therefore the same abstract complex.

Proof. The map $H:P\times\{0<1\}\to Q$ defined by $H(p,0)=a(p)$ and $H(p,1)=b(p)$ is order preserving. The only mixed comparison needing verification is $(p,0)\le(p',1)$, which implies $p\le p'$ and hence $a(p)\le a(p')\le b(p')$. The order complex of this product triangulates each prism over a chain of $P$: a chain $p_0<\cdots<p_s$ is crossed with an interval and split at each possible transition from level zero to level one. These prism triangulations agree on shared faces. Realizing $H$ gives a continuous homotopy from the realization of $a$ to that of $b$. □

The maps $gf$ and $fg$ of Equations (47) and (48) are order preserving and lie above the identity. Applying Theorem A.1 gives both homotopies required there. This avoids choosing a maximal face for each simplex, which would obscure naturality when the failure rule changes.

An alternative intermediate model is the order complex of the winning-face poset $P_{\mathcal{F}}$. Define

and

These are order preserving, $ut$ is the identity, and $A\subseteq tu(A)$. Thus $\Gamma_{\mathcal{F}}$ is also homotopy equivalent to the winning-face order complex. For the cardinality rule, this is the subcomplex of the barycentric nerve subdivision on faces of size at least $k$, connecting the present formulation directly to the classical multicover nerve [3]. The map $u$ commutes with inclusions of winning-face sets at fixed $N$.

A chain comparison for the disk covers

This appendix explains the natural homology statement in the semialgebraic disk setting without treating an arbitrary closed cover as an open good cover. A finite family of compact semialgebraic sets admits a common finite compatible triangulation [8, 12]. Apply this to the finitely many disk intersections appearing in the secondary covers under consideration. Each such set is represented by a subcomplex of a common finite complex $L$. Every nonempty finite intersection remains contractible because it is convex before triangulation.

Index one cover by a finite set $I$, write $L_i$ for its subcomplexes and $L_A=\bigcap_{i\in A}L_i$. Over a field, form the double-chain groups

omitting empty intersections. The vertical boundary is the simplicial boundary of $L_A$. The horizontal boundary is the alternating sum of inclusions obtained by dropping one index of $A$. The standard total sign convention makes the total differential square to zero; over $\mathbb{F}_2$ the signs disappear.

Augment horizontally to the chain complex of the union. For a fixed simplex $s$ of the union, let $I_s=\{i:s\in L_i\}$. This set is nonempty. Its copies in the augmented row of Equation (B.1) form precisely the augmented chain complex of the full simplex on $I_s$. That complex is exact: fixing one index in $I_s$ and adjoining it gives a contracting homotopy. Splitting the row over the simplices $s$ proves horizontal exactness. Thus the total chain complex computes the homology of the union.

Boundary arithmetic and exact input semantics

Binary columns over F2

Number the dual edges from zero to $E-1$. A triangle with edge indices $a,b,c$ has boundary column

where $\oplus$ is bitwise exclusive-or. This is simply an encoding of a vector in $\mathbb{F}_2^E$; it is not integer linear algebra. Each edge has two vertex endpoints, so applying the edge boundary to a triangle boundary counts every vertex twice. Therefore $\partial_1\partial_2=0$.

To compute the rank, maintain at most one pivot column for each leading nonzero row. A new column is repeatedly added to the stored column with the same leading row until it becomes zero or acquires a previously unused leading row. In the latter case store it. Every reduction step preserves the span of columns seen so far. Stored columns have distinct leading rows and are linearly independent. Each processed column is in their span, so the number stored is exactly the boundary rank. Termination follows because the leading nonzero row strictly decreases.

One may instead represent columns by sets and use the smallest nonzero row. That leading row strictly increases. The same span invariant proves correctness for every finite input, independently of the chosen representation or pivot direction.

Rational comparisons and equality

All inputs are rational. Products, sums and divisions in Equations (52), (54) and (55) therefore have exact integer numerators and denominators. The only radicals are eliminated by the signed comparisons of Theorem 11.4. Unconditional squaring would be wrong when the compared sides have uncontrolled signs; the sign cases are part of the algorithm.

A floating-point input is a dyadic rational $m2^e$ and is treated as that rational.

No geometric epsilon is used to merge circles, enlarge radii or decide tangency. Equal centers are tested as exact rational pairs. Coincident disks retain distinct labels because a failure model can distinguish the two contacts even when their geometry is identical. Equality in a closed-disk test is accepted; open disks, as in [2], require strict inequalities throughout.

D Counterexamples to stronger interpretations

Example D.1 (Hole-free does not imply target coverage). Let $D_1$ be the unit disk at the origin and let the target be the unit disk centered at $(10, 0)$. The ordinary covered region is contractible and has $b_1 = 0$, but its intersection with the target is empty. No theorem using only the absolute Betti numbers of the covered region can certify containment of every possible externally supplied target.

Example D.2 (Pairwise overlap does not determine a triangle). Three disks centered at the vertices of an equilateral triangle of side $d$ overlap pairwise when $r \ge d/2$, but share a common point only when $r \ge d/\sqrt{3}$. For $d/2 < r < d/\sqrt{3}$, their nerve contains a cycle without a filled triangle. Replacing the nerve by the flag complex of pairwise overlaps changes $H_1$. The same issue appears again in the facet-intersection model, as noted after Theorem 10.6.

Example D.3 (Geometric uncertainty can hide temporary homology). Even when an inner region and an outer region are both disks, an intermediate subset containing the inner disk and contained in the outer disk can be an annulus attached to that disk, or a disk with a separate small component. Thus knowledge of endpoint Betti numbers alone does not determine all intermediate Betti numbers. The rank lower bound after Theorem 12.5 is the conclusion that follows from the factorization; a stronger exactness assertion would require additional hypotheses.

E Finite minimax and rational protection certificates

We give the finite minimax argument used in Theorem 8.1. This is a classical duality principle. The proof is included to make the verification inequalities and their attainment transparent.

The weak-duality chain in Theorem 8.1 proves optimality from these finite checks. No simplex basis or floating-point tolerance is involved. The conclusion does depend on the completeness of the geometric cut list, which is justified separately by Theorem 4.1 or Theorem 5.6.

Direct derivations for the four-corner panel

Let $a=3/5$, let $T=[-a,a]^2$, and place the four sites at $(\pm1,\pm1)$. For a target point write $u=\max\{|x|,|y|\}$ and $v=\min\{|x|,|y|\}$. Then $0\le v\le u\le a$. The ordered squared distances are

Each is convex on the triangle with vertices $(0,0)$, $(a,0)$ and $(a,a)$, so its maximum there is attained at a vertex. It follows that

with $\max_T d_3^2=2+2a+a^2$. These give all four contact thresholds independently of the support algorithm, including every step of Equation (65).

At any generic target point the two nearest corners share an edge. At a tie, the active group contains such a pair. Since $(9/5)^2>68/25$, every active set at nominal radius $9/5$ contains an adjacent pair. At $(-11/20,0)$ the squared distances to the left corners are $481/400$, while those to the right corners are $1361/400$. They lie on opposite sides of $81/25=1296/400$, giving exactly the left pair. The three symmetric locations give the other adjacent pairs. This proves Equation (64) directly.

Column and diagonal domains

To tolerate a column-domain loss, either column alone must cover $T$. The farthest target point from the nearer site in a surviving column is the midpoint of the opposite target edge. Its squared distance is $(1+a)^2+1=89/25$.

For the diagonal containing $(1,1)$ and $(-1,-1)$, the nearer squared distance is

On each side of the line $x+y=0$ this is a squared norm to one fixed corner, hence convex. Its maximum over the two triangular halves of $T$ occurs at their vertices, giving $2+2a^2=68/25$. The other diagonal has the same value. These calculations prove the distinct domain thresholds directly.

Box displacement uncertainty

Give every site independent coordinate errors in $[-b,b]^2$ with $b=1/10$. Throughout $T$, the farthest allowed center for a corner site is its outward shifted corner $(\pm(1+b),\pm(1+b))$. This follows coordinatewise because target coordinates stay strictly between the nominal corner coordinates. Thus, restricted to $T$, the guaranteed distance for each physical contact is the distance to that one outward center.

Repeating the ordered-distance calculation with corner magnitude $1+b$ gives the two-contact critical square

This independently verifies the sixteen-primitive bundle computation. The reduction to one outward corner is special to this target’s position inside the nominal square; the general uncertainty algorithm keeps all four box vertices.

The three target patches

For the three-asset example, the farthest point of each triangular patch from either of its two intended centers is one of the patch vertices, by convexity of squared distance. Direct substitution gives values below $(6/5)^2$. At the patch about $(0,0)$, every point has distance at least $3/2-\sqrt{2}/20>6/5$ from the third center. At the other patches the corresponding pair midpoint has distance $\sqrt{45}/4$ from the excluded center, and subtracting $\sqrt{2}/20$ still exceeds $6/5$. Hence each patch has exactly its intended pair of active contacts. The three masks and odd-cycle obstruction follow.

The exact state reliability is $1-3p^2+2p^3$. The protection allocation and dual distribution both equal $(1/3,1/3,1/3)$, with value $2/3$. Thus the geometry, coloring, reliability and optimization conclusions for this example each have a direct derivation as well as an executable control.

Support degeneracies and boundary conventions

Coincident sites

Coincident physical contacts have equal distance functions everywhere but can have different failure labels. The support proof groups their equal geometric positions while retaining every label in the winning predicate. A collection of coincident sites supplies no independent bisector equations. If fewer than $f$ independent restricted differences occur at a candidate maximizer on an $f$-face, the tangent-direction contradiction in Theorem 5.4 still applies.

Collinear triples

In the plane, three distinct collinear centers cannot all be at the same distance from a point, since a circle meets a line in at most two points. They therefore do not determine a finite circumcenter and are skipped by the support construction. A nonsingular triple uses two exact linear equations. Near-collinearity changes rational denominator sizes but does not justify replacing the determinant by a tolerance.

An edge coinciding with a bisector

If a target edge lies on a site-pair bisector, that equality gives no isolated support point on the edge. Along it, the two distances remain equal and their common square is a strictly convex quadratic in an edge parameter. A relative interior maximum therefore requires a further threshold tie, or else occurs at an endpoint. The extra tie yields a triple support; the endpoints are already supplied target vertices. This is the rank test in Theorem 5.4, not a missing numerical special case.

Why open footprints change the fixed-radius question

For closed footprints, coverage at the critical common radius is accepted: $r \ge r_w^*$. With open disks, equality may fail at a maximizing witness. Moreover, interior-cell masks alone need not describe coverage of all target boundary points by open sets. The vertical target theorem and its closed-set witness lemma are therefore not silently transferred to strict inequalities.

Why lower-dimensional targets need their own strata

An isolated target point on a disk tangency can have an active mask absent from every two-dimensional cell. A target containing a line segment as a separate appendage can have the same issue on that segment. The regular-closed target hypothesis excludes these cases from the full-dimensional sweep. The common-radius support theorem itself can be applied face by face to prescribed simplices of the appropriate dimension, but that is a different stratified input specification.

Declarations

Funding. None.

Competing interests. None.

Ethics. Not applicable; the article contains no research involving human participants or animals.

Data availability. The LaTeX source and the finite checks of the worked examples are archived in the repository https://github.com/creelie/sensor-resilience-certificates, release v1.1.1, on Zenodo at doi:10.5281/zenodo.23742526. No statement of the paper depends on them. OpenAI Codex and Anthropic Claude assisted with exposition, figures and the finite checks; the authors checked every proof and are responsible for the text.

References