Finding solutions with the Borsuk-Ulam theorem

Introduction

The Borsuk–Ulam theorem is a source of existence results in combinatorics and geometry. A common strategy is to describe the desired configuration as a zero of a continuous map and use symmetry to prove that such a zero exists. The purpose of this paper is to develop the numerical side of this strategy. When a simple instance of the problem has a single known solution, can we follow that solution as the simple instance changes into the one we want to solve?

The ham-sandwich theorem gives a familiar example: any $d$ bounded regions of positive volume in $\mathbb{R}^{d}$ can be simultaneously bisected by one affine hyperplane. In the plane, one line divides each of two figures into equal areas; in space, one plane halves each of three objects. The regions need not be convex or connected, and they may overlap. To see the connection with topology, represent an oriented hyperplane by its normalized coefficients. Including the two limiting positions gives a sphere $S^{d}$ of parameters. Record, for each region, the fraction of its volume on the positive side minus one half. Reversing the orientation changes all signs. We therefore obtain a continuous odd map $f:S^{d}\to\mathbb{R}^{d}$. The classical Borsuk–Ulam theorem says that every such map has a zero, which is exactly a common bisector [23, 17]. Thus ham-sandwich cuts belong directly to the class considered here.

A simple starting instance consists of $d$ balls whose centers are affinely independent. A hyperplane bisects a ball precisely when it passes through its center, so this instance has exactly one unoriented bisecting hyperplane. Smooth radially symmetric versions provide the models used in our numerical analysis. We also consider orthogonal partitions, where several mutually perpendicular cuts must satisfy simultaneous balancing conditions; their parameter space replaces the sphere by an orthogonal group [20, 21].

Here is the continuation idea. Let $M$ be the space of possible configurations, let $f(x)=0$ express the target problem, and let $g(x)=0$ express the known model. Join the two maps by

Every horizontal level of the cylinder $M\times[0,1]$ represents an intermediate problem. Under regularity assumptions, its solutions, viewed together in the cylinder, form curves. Figure 1 shows the essential argument, with symmetry-related descriptions identified. The curve starting at the unique model solution cannot return to the bottom: an interval has two distinct endpoints, and there is no second model solution. It must reach the top. Other target solutions can be joined to one another by separate curves.

This geometric argument appears in the proof of the Borsuk–Ulam theorem in Matoušek [17, Section 2.2], following constructive proofs such as [3, 18]. It extends to manifolds with suitable finite-group symmetries [19]. Theorem 2.1 states the continuation principle in this setting. A regular curve may turn back in the parameter $t$; following the curve and always increasing $t$ are therefore different requirements. We specify the additional condition for the latter, and also discuss how to follow curves through turns.

Numerically, we take a small step along the solution curve and correct the resulting error before taking the next step. Theorem 3.1 bounds the step and the error, while Proposition 3.4 includes the cost of evaluating the equations to the required accuracy. These estimates use the stability of the local equations along the chosen curve. Homotopy continuation is classical [1, 7, 2]; our contribution is to connect the one-solution model with explicit tracking estimates and the maps needed for mass partitions.

For finite point sets, a bisector leaves at most half of each set in either open half-space; points on the plane are excluded from both counts. The counts jump when a plane crosses a point. We therefore spread each point into a small mass, solve the smooth problem, and recover a discrete cut. For odd set sizes and points avoiding affine degeneracies, every exact bisector passes through one point of each set. These points allow exact reconstruction from a sufficiently accurate smooth answer (§ 5).

A single continuation finds one solution. Changing the model can lead to different endpoints: for ham-sandwich cuts, suitable model centers reach every regular cut (Theorem 6.2).

We explore these parameters and record the answer in each region. Regions leading to the same answer may be disconnected. § 6 gives conditions for a finite search without a connectedness assumption.

With dimension fixed, each step takes linear arithmetic work in the total number of points. The full computation has this linear cost when accuracy and the geometric bounds controlling its steps are uniform over the input family. Lo, Matoušek, and Steiger [15] give an optimal linear-time planar ham-sandwich algorithm, and Fakhrutdinov and Musin [9] obtain optimal linear time for planar orthogonal four-partitions. Their general constructions have polynomial bounds whose exponents grow with dimension. On families satisfying our tracking bounds, continuation offers a numerical approach with linear cost. As in [22, 5], we distinguish path-dependent step counts from the cost per step.

Zero arcs and PL continuation

We first give the topological conditions that make a solution curve reach the target. The smooth argument uses regular arcs; its piecewise-linear counterpart follows a finite chain of segments.

Let $n \ge1$ and let $M$ be a closed smooth $n$-manifold, possibly disconnected, with a free smooth action of a finite group $G$. Let $V$ be an $n$-dimensional real representation of $G$. Metrics are chosen $G$-invariant. A map is equivariant if $f(ax)=af(x)$ for $a \in G$, and is regular at its zeros if its differential there is invertible. Solutions are counted modulo $G$.

Proof. The regular level theorem makes $Z=F^{-1}(0)$ a one-manifold in the cylinder’s interior. At a boundary zero, spatial invertibility expresses $Z$ as a graph over an inward collar coordinate. Thus $Z$ is a compact $C^1$ one-manifold with $\partial Z=g^{-1}(0)\sqcup f^{-1}(0)$. The free action restricts to $Z$, so $Z/G$ is also a compact one-manifold.

The component containing the unique initial zero orbit is an interval. Its two endpoints are distinct. The initial boundary contains only one point of $Z/G$, so the other endpoint must lie on the target boundary. The covering $Z\to Z/G$ is trivial over an interval; its lift through $(x_0,0)$ is the asserted arc. A finite cover by regular coordinate graphs shows that its length is finite, and the inward direction fixes its orientation.

A tangent vector $(\xi,\tau)$ satisfies $J\xi+F_t\tau=0$. When $J$ is invertible, a nonzero tangent has $\tau\ne0$. Its sign is initially positive and cannot change, so projection to $t$ is a diffeomorphism onto $[0,1]$. Differentiation gives (2). If $J$ is invertible at every zero, no zero component can be a circle or an interval with both endpoints on the same boundary: $t$ would have a critical point. Hence every quotient component joins the two boundaries, and the unique initial endpoint leaves exactly one component. $\square$

More generally, if there are $r$ initial zero orbits, $a$ quotient intervals joining two initial endpoints, and $c$ crossing intervals, then $r = 2a + c$. Odd $r$ guarantees a crossing, but does not identify a crossing from every start.

Proof. Equivariant maps correspond to sections of the associated bundle $(M \times[0,1]) \times_G V$ over the quotient cylinder. Boundary regularity gives regular collars. Choose smaller collars on which the perturbation is identically zero. On the compact complement of the larger collars, finitely many local frames multiplied by bump functions, supported away from the smaller collars, span every fiber. Adding their small linear combinations gives a transverse universal section on this compact region; on the collars transversality persists for small coefficients. Sard’s theorem applied to its zero set and projection to the coefficients gives transverse sections for almost every small choice. Smallness preserves regularity in the collars. Lifting proves the assertion.

Proof. Approximate the homotopy uniformly by smooth equivariant maps, keeping $g$ fixed. This relative approximation follows by smoothing in charts and averaging over $G$, after making the homotopy constant on a shrinking initial collar. Perturb each target to a transverse section and apply Lemma 2.2. The perturbations can tend to zero. Theorem 2.1 supplies crossing arcs with the same chosen initial lift $(x_0,0)$. A subsequence converges in Hausdorff distance, since the space of nonempty compact subsets of the cylinder is compact. Its limit contains $(x_0,0)$ and meets the closed target boundary, lies in the original zero set by uniform convergence, and is connected: a separation into disjoint compact sets would separate all sufficiently close arcs. This is the connectedness theorem for Hausdorff limits of compact connected sets. Apply this to (1) for the last assertion.

This limiting connected set need not be an arc. Numerical path following therefore uses the rank assumptions, not just the continuous existence statement. The same quotient-interval proof works on a compact free $G$-bordism with the prescribed boundary maps; this is the setting of [19], Theorem 1. Both applications here use cylinders.

Example 2.4. For the antipodal circle,

The selected branch is $\theta= 0$, with $F_\theta= 1 + 2t > 0$. The target has three zero orbits. The other two are joined by the arc $t = (4\sin^2\theta- 2)^{-1}$, $\pi/3 \le\theta\le2\pi/3$, with a fold at $(\pi/2,1/2)$. There $F_t = -2$, so the full zero curve is regular. Replacing $F(\theta,t)$ by $F(\theta- 2j\pi/3,t)$, for $j = 0,1,2$, preserves both endpoint maps but selects the three different target orbits. Thus the endpoint depends on the homotopy.

Proof. The dimension count is $(n+1)-n=1$ in a top simplex, $n-n=0$ in an $n$-face, and negative in smaller faces. Thus crossings of $n$-faces are allowed; only the $(n-1)$-skeleton is excluded. In a top-dimensional simplex with vertices $v_i$, the zero set is

A vertex of this polytope has at most $n+1$ positive coordinates. Skeleton avoidance forces exactly $n+1$, and the corresponding columns $(1,F(v_i))$ are independent: otherwise a dependence could move positive coordinates until one vanished, giving a forbidden zero. The nonempty zero polytope is consequently a line segment. Its endpoints lie in interiors of $n$-faces; invertibility of the face matrix lets a zero extend into either adjacent top simplex. Interior faces have two such simplices and boundary faces one. The segments therefore form a finite one-manifold. The quotient interval argument proves the assertion. The selected interval cannot revisit a segment, and its endpoints are solutions of linear systems with the given vertex values.

This is the finite path construction underlying the PL proofs in [17 Section 2.2] and [19 Lemmas 3–5].

Small-step continuation

The preceding section supplies a path. We now construct small steps that stay near it and bound the error left after each correction.

Write $J=D_xF$ and $b=F_t$. In a local chart the method is

These are tangent prediction and one Newton correction. On a manifold the additions are chart operations. The gradient of $\lVert F\rVert^2/2$ vanishes at zeros and does not itself give a continuation direction.

Here and below the tracking bounds first refer to exact arithmetic. We give explicit constants and then account for evaluation errors. In a fixed Euclidean chart assume, on the tube $\lVert y-x(t)\rVert\le\rho$, that

where $L>0$ bounds the full Hessian. Put

Proof. Differentiate $F(x(t),t)=0$ twice: $Jx'+b=0$ and $Jx''+D^2F[(x',1),(x',1)]=0$. These give the first bounds. For $e\le r$, the coordinate segment from $x(t)$ to $y$ stays in the radius-$\rho$ tube. The Hessian bound gives

Thus $\sigma_{\min}(J(y,t))\ge\alpha-Le\ge3\alpha/4$ and $\lVert J(y,t)^{-1}\rVert\le2/\alpha$. Subtracting the two velocity equations gives

which proves (8); Taylor’s formula gives (9). With $x=x(t)$, the Newton error is

Its norm is at most $Le^2/\alpha$. Expansion at $x$ gives the lower residual bound $\alpha e-Le^2/2\ge\alpha e/2$; integration of $J$ gives the upper bound.

Proof. Around each point of the graph choose a smaller chart neighborhood compactly contained in a larger one, and a time interval whose closed graph segment lies in the smaller neighborhood. Smooth charts are locally bi-Lipschitz; shrink these neighborhoods so that both inequalities hold there. A finite subcover gives a common $Q$ and positive coordinate and intrinsic margins. Decreasing $\rho$ secures both ball inclusions. Choose $h_{\mathrm{ch}}$ smaller than a Lebesgue number of the time cover. Compactness, continuity of the derivatives, and invertibility of $D_xF$ on the graph give uniform bounds on the resulting tubes.

Proof of Theorem 3.1. First use a fixed chart and take $h_0=h_*$, $\eta_0=\eta$. An error $e\le r/8$ gives predictor error at most $2e+r/4\le r/2$. Correction gives error at most $\kappa r^2/4\le r/16$, so every step stays in the tracking tube. For the sharper estimate put $q=Ch^2/2\le r/4$. An error at most $q$ gives predictor error at most $3q$ and corrected error at most $9\kappa q^2\le q$, since $9\kappa q\le9/16$. Starting at zero error, induction yields

The error left by each preceding correction is included in this induction. At the target, $e_{j+1}\le\kappa e_j^2$ and $\kappa e_0\le\kappa\eta\le1/32$, whence $e_j\le\eta\,2^{-(2^j-1)}$. Taking $C_1=\Lambda\eta$ proves (5). Residual $\delta$ implies coordinate error at most $2\delta/\alpha$. For a manifold, use Lemma 3.3. At each step choose a chart containing its whole graph segment and use this chart for both prediction and correction. Set

Write $E_k=\operatorname{dist}(y_k,x(t_k))$ and $e_k=\lVert\psi_j(y_k)-\psi_j(x(t_k))\rVert$ in the chart used for that step. Equation (11) gives $e_k\le QE_k$ and $E_{k+1}\le Qe_{k+1}$, including when the next step uses a different chart. Intrinsic error $\eta_0$ becomes coordinate error at most $r/(8Q^2)$; prediction and correction bound it by $r/(2Q^2)$ and $r/(16Q^4)$, respectively. Returning to intrinsic distance preserves $\eta_0$. Now $q=Ch^2/2\le r/(4Q^2)$. Intrinsic error at most $q/Q$ gives corrected intrinsic error at most $9Q\kappa q^2\le q/Q$. Induction gives $C_0=(9/4)Q\kappa C^2$. At the target the coordinate error is at most $r/(8Q^2)\le\eta$, so the same final Newton bound applies. $\square$

If a complete prediction–correction step costs $\mathcal{W}$ and an endpoint Newton iteration costs at most the same amount, the total arithmetic work is

This separates the continuation count from the representation of the map.

Local steps and inexact correction

The global bounds above can be replaced by local tests as the computation advances. We also allow errors in function evaluation and in solving the linear systems. At $(y,t_0)$ let $A=J(y,t_0)$, $\beta=\lVert A^{-1}\rVert$, $v=-A^{-1}b(y,t_0)$, $d_0=\lVert A^{-1}F(y,t_0)\rVert$, and $W=\sqrt{1+\lVert v\rVert^2}$. Suppose $\lVert D^2F\rVert\le L$ on the predictor tube

If

each slice contains exactly one zero in its radius-$R$ ball, and these zeros form a regular graph. Indeed, $T_s(u)=u-A^{-1}F(y+sv+u,t_0+s)$ has derivative norm at most $1/2$, while $\lVert T_s(0)\rVert\le R/2$ by Taylor expansion and $Av+b=0$. The contraction theorem and the implicit function theorem prove the claim. If the selected initial zero lies in the first ball, uniqueness identifies this graph with its continuation.

Use separate error bounds $\tau_F,\tau_J,\tau_b$ for evaluating $F,J,b$, in the fixed coordinate and target norms. Let $\tau_p$ and $\tau_c$ bound the residuals in the predictor and corrector linear solves, respectively. If $\tau_J\le\alpha/4$, then $\lVert\widetilde{J}^{-1}\rVert\le2/\alpha$ throughout the radius-$r$ tube. Subtracting the predictor equations, with $v=-J^{-1}b$, gives

For correction, put $\zeta=\tau_J$ and $\tau=\tau_F+\tau_c$. The Newton integral identity gives, for predictor error $e\le r$,

These tolerances enter with different factors; they need not be equal. For example, use $h\le\min\{1,D^{-1},\sqrt{r/(4C)}\}$, velocity error at most $\xi$ with $h\xi\le r/8$, $\xi\le\alpha/32$, and $\tau\le\alpha r/64$. Starting with $e\le r/8$, prediction gives error at most $r/2$; the three terms in (17) are then at most $r/16,r/32,r/32$, preserving $r/8$ after correction. At $t=1$ the valid residual test is $\lVert\widetilde{F}(y,1)\rVert+\tau_F\le\delta$. Quadratic refinement requires decreasing evaluation errors: $\zeta=O(e)$ and $\tau=O(e^2)$ suffice.

For $C^1$ maps a sufficiently small step still works, but quantitative bounds require moduli of continuity. In a fixed tube let $\omega_J,\omega_b$ be spatial moduli for $J,b$, let $V=\max\|x'\|$, and set $\nu(s)=2(\omega_b(s)+V\omega_J(s))/\alpha$. Choose $r$ with $\omega_J(r)\le\alpha/8$, and let $\omega_v$ be a modulus for $x'$. For $e\le r/8$ the predictor error is at most $e+h\nu(e)+h\omega_v(h)$. Choose $h$ so that the last two terms are at most $r/8$ and $r/4$. The predictor error is then at most $r/2$, and Newton’s integral identity gives $e_{\mathrm{new}}\le(2/\alpha)\omega_J(e)e\le e/4\le r/8$. This proves finite tracking and convergent final refinement. Finite charts with smaller radii give the manifold statement.

Residual accuracy and evaluation cost

An approximate answer should have an error that can be checked from the equations themselves. This leads to a common accuracy criterion for the different applications.

An $\varepsilon$-solution of the Borsuk–Ulam equation $f(x)=0$ means a point $y$ with $\|f(y)\|\le\varepsilon$. The norm and normalization of $f$ are fixed as part of the problem. This accuracy is meaningful even when an approximate zero need not be close to a uniquely specified exact zero.

Proof. The coordinate endpoint error is at most $QC_0h^4$. Integrating $D_xF$ along the coordinate segment to the zero gives the first assertion; multiplying the step cost by $K$ proves (19).

For the inexact assertion take $\tau=h^4$. On a smaller tracking tube, perturbed Jacobians have uniformly bounded inverses. Equation (16), with $\|v\|\le V+Dr$, bounds the velocity error by $C_vh^4$ for a fixed $C_v$. Put $P=C/2+1$ and $A=Q(\kappa P^2+2P/\alpha+4/\alpha)$. If the intrinsic point error is at most $Ah^4$, its predictor error in the current chart is at most

for sufficiently small $h$. Further decrease the step bound so that the predictor lies in the tube and $h^4\le\alpha/4$. The value error and corrector solve residual contribute at most $2h^4$ together. By (17), the new intrinsic error is at most

Induction from the exact initial zero proves the estimate in every chart. Take $\widehat R_0=\Lambda QA$ and choose $\widehat h_0\le h_0$ to satisfy the preceding restrictions. This proves (20). For sufficiently small $\varepsilon$, $K=O(\varepsilon^{-1/4})$ and $K^{-4}\ge c\varepsilon$; monotonicity of the cost bound proves (21). ▫ The estimate is common to the smooth Borsuk–Ulam problems considered here, with dimension fixed. Its constants describe the selected regular branch; $W(\tau)$ describes how the input is evaluated, including integration when needed. No rate depending only on $\varepsilon$ follows from the topological existence theorem. In particular, the $C^1$ case above requires moduli of continuity, and a fold requires the augmented system below. For a computed value with certified error $\tau$, the stopping test is $\lVert\tilde{f}(y)\rVert+\tau\le\varepsilon$. If only the endpoint requires higher accuracy, final Newton refinement can be used instead of reducing all continuation steps; its exact-arithmetic count is (5). In Gaussian applications, $W(\tau)$ includes evaluation of $\Phi$ and $\phi$ to the requested tolerances. Counting these functions at unit cost, as in § 5.3, is a separate real-arithmetic model, not a bit-complexity assertion.

Folds

The extra equation below controls progress along the solution curve without requiring the homotopy parameter to increase.

At a regular zero write $A=DF$ and choose the oriented unit vector $q\in\ker A$. Pseudo-arclength prediction $z_p=z+hq$ uses the corrector

Its derivative at the current zero is $\mathcal{A}=(A^{T},q)^{T}$, which is invertible since $\ker A=\mathbb{R}q$. In orthonormal coordinates its singular values are those of $A$ together with $1$.

For a compact $C^2$ regular arc, sufficiently small steps therefore follow it through folds. Here is the needed finite-step justification. In arclength coordinates, $Az''+D^2F[z',z']=0$ and $\langle z',z''\rangle=0$, so $\lVert z''\rVert\le L/a$, where $a$ is a lower bound for the smallest positive singular value of $A$. The predictor error is $O(h^2)$; the correction plane meets the same local arc at arclength advance $h+O(h^2)$ because its derivative along that arc is $1+O(h)$. Compactness gives uniform inverse bounds, chart margins, and Newton neighborhoods. Taking the point error $O(h^2)$ and tangent error $O(h)$ preserves this advance. Such tolerances are attainable by Newton correction and continuity of the kernel direction, with orientation chosen by the preceding tangent. Every sufficiently small accepted step advances at least $h/2$. An arc of length $\ell$ thus requires $O(1+\ell/h)$ steps to a target neighborhood, followed by Newton correction on $t=1$. These constants concern the augmented system; the monotone bounds above are not applied at a fold.

Ham-sandwich and orthogonal partitions

Each application requires explicit balance equations and a model whose solution is known. We construct both and give geometric criteria for applying the numerical estimates.

A probability measure is hyperplane-null if every affine hyperplane has measure zero. A positive Schwartz density is a strictly positive smooth function of integral one, all of whose derivatives decrease faster than any inverse power at infinity.

Ham-sandwich cuts

We justify the spherical description from the introduction and identify the local geometry that makes a bisector regular.

Use $S^d=\{(a,w)\in\mathbb{R}\times\mathbb{R}^d:a^2+\lVert w\rVert^2=1\}$. For $d$ hyperplane-null probability measures on $\mathbb{R}^d$, set

At the poles set $f_i(1,0)=-1/2$ and $f_i(-1,0)=1/2$. Dominated convergence at finite hyperplanes and tightness at the poles prove continuity. Boundary nullity gives oddness, and zeros are exactly the common bisecting hyperplanes, modulo orientation. For $w\ne0$, unit-normal coordinates are $(a/\lVert w\rVert,w/\lVert w\rVert)$. Below the offset in these coordinates is again denoted by $a$.

Take model measures $\nu_i=\mathcal{N}(c_i,I_d)$, where $c_1=0$ and $c_i=e_{i-1}$ for $2\le i\le d$. Their map is

where $\Phi$ and $\phi$ denote the standard normal distribution and density. A Gaussian is bisected precisely by hyperplanes through its center. These centers span $x_d=0$, so the only zeros are $\pm(0,e_d)$. At $(0,e_d)$,

The first row forces $\delta a=0$ and the remaining rows force $\delta w_1=\cdots=\delta w_{d-1}=0$. The model is regular, also for $d=1$.

For a positive Schwartz density $\rho_i$, the map is smooth. Away from the poles this follows by differentiating under the integral; near the poles rapid decay makes the tails and all their derivatives tend to zero faster than any power of $\lVert w\rVert$. In unit-normal coordinates $H=\{x:u\cdot x=a\}$, put

Writing $x=z+su$, $z\perp u$, and differentiating the moving lower endpoint of the half-line integral gives

Rapid decay justifies differentiation. Since all centroids belong to $H$, a kernel vector satisfies $(c_i-c_1)\cdot\delta u=0$ for $i\ge2$ and $\delta a=c_1\cdot\delta u$. Consequently $Df$ is invertible exactly when the $d$ section centroids are affinely independent.

Proof. The derivative and kernel calculation above give the factorization and equivalence. The singular-value bound follows by applying $\lVert\operatorname{diag}(m_i)z\rVert\ge(\min_i m_i)\lVert z\rVert$ to $z=C_Hv$.

Proof. Apply Proposition 2.3 to the odd map (23) and the regular model (24). Its zero is not a pole and hence gives a finite bisector. The smooth continuation statements follow from the derivative criterion and Theorems 2.1–3.1.

For the mixture homotopy, $\lVert F_t\rVert\le\sqrt{d}$. An alternative model uses centered regular-simplex centers in $e_d^\perp$, normalized by $\sum_i c_i=0$ and $\sum_i c_i c_i^T=I-e_de_d^T$. Direct expansion gives

Thus the model has smallest singular value $\phi(0)$ independently of $d$; this is an initial bound, not a bound along the homotopy.

Accuracy for measures. For the normalized measures above, the mass error of a hyperplane is

Since hyperplanes have zero mass, the opposite half-space has the same error. Thus the residual estimate in Proposition 3.4 gives an $\varepsilon$-bisector in mass. For unnormalized finite positive measures, normalization makes this an error of at most $\varepsilon$ times each total mass. Here $W(\tau)$ includes the half-space integrals and the section integrals determining their derivatives in (25), to the required accuracy.

If the input measures are approximated by probability measures $\widetilde{\mu}_i$, the appropriate error for this problem is their discrepancy on half-spaces:

Directly from the triangle inequality,

Consequently discrepancy at most $\varepsilon/2$ and a certified mass error at most $\varepsilon/2$ give an $\varepsilon$-bisector of the original measures. For densities, the discrepancy is at most $\frac{1}{2}\max_i \|\rho_i-\widetilde{\rho}_i\|_{L^1}$: their difference has integral zero, so its positive and negative parts have equal integrals. Constructing the approximate measures is a separate input cost. Discrepancy controls the final mass error; derivative and conditioning bounds must still be checked for the homotopy actually tracked.

Orthogonal pairwise four-partitions

Here the unknown is an orthogonal frame. Individual bisection determines the offsets, leaving the pairwise balance equations.

The pairwise orthogonal partition theorem was stated by Makeev [16]; the equivariant model used here is from [20]. Let $B_d$ be the signed permutation group and let $W_2^+$ be the space of symmetric $d \times d$ matrices with zero diagonal. Use the left actions $P \cdot U = UP^{-1}$ on $O(d)$ and $P \cdot C = PCP^{-1}$ on $W_2^+$. The first is free and both spaces have dimension $n = \binom{d}{2}$. For a diagonal matrix $A_0 = \operatorname{diag}(\alpha_1,\ldots,\alpha_d)$ with distinct entries, set

Since signed permutations preserve diagonal matrices, $g(UP^{-1}) = \operatorname{off}(PU^{T}A_0UP^{-1}) = Pg(U)P^{-1}$. Thus the map is equivariant, and $g(U) = 0$ means that the columns of $U$ are eigenvectors of $A_0$. Its zeros are exactly the signed coordinate eigenbases, one $B_d$-orbit. For $\Omega^T=-\Omega$,

by differentiating $e^{-s\Omega}A_0e^{s\Omega}$. These are independent tangent coordinates with nonzero coefficients. Equivariance gives regularity at all zeros. This is the model of [20].

Let $\rho$ be a positive Schwartz probability density. For each unit $u$ there is a unique median offset $a(u)$, since the half-space mass decreases strictly from $1$ to $0$ with derivative

The implicit function theorem gives smoothness, and $a(-u)=-a(u)$. For $U=(u_1,\ldots,u_d)$ put $s_i(x)=\operatorname{sgn}(u_i\cdot x-a(u_i))$ and

Signs and permutations of the columns give the stated equivariance. Orthogonal coordinates and translation by the offsets express the quadrant masses as integrals over fixed orthants, proving smoothness. The median equations give $\int s_i\rho=0$, and therefore

Zeros of $f$ are precisely the pairwise four-partitions. This asserts equality of the four parts for every pair; it does not assert equality of all $2^d$ orthants.

For evaluating the Jacobian, let $H_i=\{u_i\cdot x=a(u_i)\}$ and let $c_i$ be its section centroid. Differentiating the median equation gives $Da(u_i)[\delta u_i]=c_i\cdot\delta u_i$. The jump of a sign function is 2, so

Use local orthogonal coordinates and differentiate the integrals on each side of the moving boundaries. Schwartz decay justifies dominated differentiation, and $H_i\cap H_j$ has surface measure zero in either hyperplane. The boundary terms give the displayed formula. Setting $\delta U=U\Omega$ gives the square Jacobian in the $\binom{d}{2}$ independent entries of $\Omega$. Prediction and correction can be performed in charts $\Omega\mapsto U\exp\Omega$.

Proof. For positive Schwartz densities, Proposition 2.3 gives a zero of (31); equation (32) proves the partition assertion. For a general hyperplane-null measure $\mu$, choose finite positive Gaussian mixtures $\mu_j$ converging weakly to $\mu$. Finitely supported approximations followed by Gaussian convolution provide such a sequence.

Choose a ball which is a continuity set of $\mu$ and has mass greater than $1/2$. It eventually has $\mu_j$-mass greater than $1/2$, so all median hyperplanes of the constructed partitions meet this ball. Their offsets are bounded. Compactness of $O(d)$ and of the offset interval gives convergent frames and offsets. The limiting frame is orthogonal. On any fixed ball the defining affine functions converge uniformly, so the moving quadrants lie between small inward and outward shifts of the limiting quadrants. Weak convergence applies to shifts chosen as continuity sets. Let the shifts tend to zero, using nullity of the limiting hyperplanes, and then let the ball grow, using tightness. All quadrant masses converge to $1/4$.

The regularity and equivariance of the model were checked in (30). Applying the two continuation theorems proves the numerical statement.

For either application a regular target permits an interior perturbation by Lemma 2.2. A prescribed linear homotopy need not already be regular or monotone.

Finite point sets

The objective here is to turn an approximate smooth partition into an exact statement about point counts.

Let $P_1,\ldots,P_d\subset\mathbb{R}^d$ be finite nonempty sets, $n_i=|P_i|$, and $N=\sum_i n_i$. A discrete bisector has at most $\lfloor n_i/2\rfloor$ points of each color in either open half-space. Points on the hyperplane are excluded from both counts. Small-ball smoothing and reduction to odd cardinalities are classical devices; see [17 Section 3.1].

Smoothing and regular target zeros

We identify conditions under which the smoothed problem has isolated, stable solutions corresponding to the discrete cuts.

Replace each point by $\mathcal{N}(p,\sigma^2 I_d)$, with equal weights within each color. For $H=\{u\cdot x=a\}$, $\lVert u\rVert=1$, write $s_p=u\cdot p-a$. The mass imbalance and its derivative are

These finite sums require no multidimensional integration. They give the smooth odd target of § 4.

Proof. If $\lVert p\rVert\le R$ and $\delta<1/2$, monotonicity of $\Phi$ gives

For instance, when $a>R$ every summand is at most $\Phi((R-a)/\sigma)$, while their average is at least $1/2-\delta$. Thus offsets are bounded and a subsequence converges, using compactness of the unit sphere. Every point strictly on one side of the limiting plane contributes asymptotically its full weight to that side. The total is at most $1/2$ in each color. Integrality gives the discrete bound on both sides.

An exact smooth cut need not be a discrete cut. For $P=\{-2,0,1\}\subset\mathbb{R}$, at the discrete median $a=0$ the Gaussian imbalance is $[\Phi(-2/\sigma)-\Phi(-1/\sigma)]/3<0$. Its strictly decreasing function of $a$ has its zero in $(-2,0)$, leaving two original points on one side. Reconstruction is essential.

From now through Theorem 5.5, assume that the sets are pairwise disjoint, all $n_i$ are odd, and their union is in affine general position: every subset of at most $d+1$ points is affinely independent. Every discrete bisector contains a point of each color, since an odd count cannot split equally off the plane. General position permits at most $d$ points on a hyperplane. Hence it contains exactly one $q_i\in P_i$, and the remaining points of each color split equally. The set $\mathcal{B}$ of unoriented discrete bisectors is therefore finite.

Parity is easily arranged: delete one point from each even-size set. If its original size is $2k$, a bisector of the remaining $2k-1$ points leaves at most $k-1$ on either side. Restoring the deleted point preserves bisection of the original set. This does not impose general position.

Compact smoothing first identifies the discrete cuts exactly. The Gaussian analogue uses a limiting argument and gives regular nearby cuts; the reconstruction theorems then allow a nonzero numerical residual. Define the slab parameter

with $r_\star=\infty$ when $N=d$. For $N>d$ the inner minimum is attained with bounded $a$ and is positive by general position; the finite outer minimum is positive. Thus a closed slab of half-width less than $r_\star$ contains at most $d$ input points.

Proof. A hyperplane meets at most $d$ support balls. To bisect an odd color it must cut the interior of at least one ball: otherwise its unnormalized half-space mass is an integer, not $n_i/2$. There is therefore exactly one such ball per color and no other ball meets the plane. Writing $n_i=2k_i+1$, its positive mass is $K_i+Q_i=k_i+1/2$, where $K_i$ is an integer and $0<Q_i<1$. Thus $K_i=k_i$, $Q_i=1/2$. Radial symmetry and positivity give the unique central median, so the plane contains the $d$ centers $q_i$ and bisects the original points. Conversely a discrete cut bisects these central balls and has equally many other balls on either side, none meeting the plane.

If $q_\kappa(0)>0$ is the central density of a one-dimensional marginal, the derivative row is $q_\kappa(0)(q_i\cdot\delta u-\delta a)/(n_i\sigma)$. The differences $q_i-q_1$ span $u^\perp$, proving invertibility. The same counting argument works for uniform balls; their map is smooth near these central cuts, though not globally $C^2$ in every dimension.

When $N=d$, the cuts coincide for every bandwidth.

Proof. At $H_0$, its signed distances $y_i=u\cdot q_i-a$ to the distinguished points form local coordinates: their derivative is invertible by the preceding kernel argument. Shrink the neighborhood so that all other points keep their sides and have distance at least $\gamma/2$. In the rescaled coordinates $y=\sigma z$, the equations are

The off-plane tails and their derivatives decay exponentially; on bounded $z$-neighborhoods they extend smoothly by zero at $\sigma=0$. The $z$-Jacobian there is $\varphi(0)I_d$. The implicit function theorem gives a unique nearby solution $z(\sigma)$ with invertible Jacobian. The bound on $E_i$ and bounded derivative of $\Phi^{-1}$ near $1/2$ give (38) and regularity.

If there were additional zeros at $\sigma_j\to0$, compactness and Proposition 5.1 would give, after choosing orientations, $H_j\to H_0\in\mathcal{B}$. First, $y_i(H_j)\to0$, because $q_i\in H_0$. Every other point has distance at least $\gamma$ from this fixed $H_0$, and eventually at least $\gamma/2$ from $H_j$. Its tail tends to zero, while its side stays fixed. The equations then give the stronger limit

Thus $(\sigma_j,z_j)$ eventually lies in the implicit-function uniqueness neighborhood, a contradiction. Finiteness of $\mathcal{B}$ gives a common bandwidth threshold. For $N=d$ the equations are simply $y_i=0$.

In a chart at $H_0$ whose tangent coordinates are $(\delta a,E\xi)$, let $C_{H_0}$ have rows $(-1,q_i^{T}E)$. The same proof and (35) give

Thus the inverse target Jacobian is $O(\sigma)$ for fixed data. This endpoint bound gives no lower singular-value bound in the interior of a chosen homotopy.

Reconstruction

The computed smooth bisector usually misses the input points. We show how the closest points determine an exact discrete answer once the bandwidth and residual are sufficiently small.

Proof. Otherwise choose counterexamples with $\sigma_j\to0$. The offset bound (36) gives a convergent subsequence with limit $H_0$. If one open side of $H_0$ contained at least $(n_i+1)/2$ points, their smooth mass would tend to at least $1/2+1/(2n_i)>1/2+\delta_0$, a contradiction. Hence $H_0$ is a discrete bisector and contains exactly one point $q_i$ per color. All others have positive distance from it, so eventually these same $q_i$ are uniquely closest to $H_j$. Their affine hull is $H_0$, contradicting the counterexample.

For an explicit bandwidth, assume $\lVert p\rVert\leq R$ and set

Let $\beta_*=\min_{q_i\in P_i}\sigma_{\min}(A(q))>0$, taking the minimum over all choices of one point from each color and using the smallest of the $d$ singular values. Each $A(q)$ has rank $d$ by affine general position; finiteness makes the minimum positive. Put $c_0=\Phi^{-1}(3/4)$ and $T=\sqrt{2\log(8n_{\max})}$.

Proof. The slab $|u\cdot p-a|\leq\rho_*$ contains at most $d$ points. Let $\delta=1/(8n_{\max})$ and $\tau=\Phi(-\rho_*/\sigma)\leq e^{-\rho_*^2/(2\sigma^2)}\leq\delta$; the normal-tail bound follows from the exponential Markov inequality. If a color had no point in the slab, its unnormalized smooth mass would be within $n_i\tau$ of an integer and within $n_i\delta$ of the half-integer $n_i/2$. This would imply $1/2\leq n_i(\tau+\delta)\leq1/4$, impossible. Exactly one point $q_i$ of each color therefore lies in the slab.

Let $k_i$ count its other points on the positive side and $s_i=u\cdot q_i-a$. Removing their tails gives

Write $m_i=(n_i-1)/2$. Since $k_i-m_i$ is an integer and $0<\Phi(s_i/\sigma)<1$, the displayed inequality forces

The last inequality uses $\sigma\leq\rho_*/T$ and $T>c_0$. Thus $q_i$ is uniquely closest. In the Euclidean coefficient space $\mathbb{R}^{d+1}$, project $h=(u,a)$ onto $\ker A(q)$ by $\widehat h=h-A(q)^\dagger A(q)h=(v,b)$. Then

Since $\lVert u\rVert=1$, one has $\lVert v\rVert\geq1-\lVert v-u\rVert>1/2$. Hence $v\cdot x=b$ is a well-defined plane through the $q_i$. No projective distance is used here. For every other point its defining affine value changes by less than $R_1\lVert\widehat h-h\rVert<\rho_*/2$, preserving its side. Each color has exactly $(n_i-1)/2$ points on either side.

This yields a practical stopping rule. After the parity reduction, choose a bandwidth and compute residual at most $1/(8n_{\max})$. Take the closest point of each color, form their plane, and check the counts in the original sets. Return it if all counts are at most $\lfloor|P_i|/2\rfloor$; otherwise halve the bandwidth and repeat. Once the residual is attained at each scale, at most

halvings suffice. The geometric minima $r_*,\beta_*$ need not be enumerated: the count check is the stopping test. For rational coordinates it uses exact linear algebra and determinant signs. A fresh model-to-target continuation may be used at each scale; regularity of one branch across all bandwidths is not assumed. The count check verifies a returned partition; it does not ensure that every attempted continuation attains the required residual.

Figure 2 shows two five-point sets. The smooth cuts each leave three original points on one side and two on the other. The line through the two closest points has two of each color on either side and one on the line.

Complexity: the number of points, step, and accuracy

Continuation complexity is naturally separated into the cost of one step and the number of steps required by the path. For polynomial systems, Shub [22] bounds the latter by length in a condition metric. Beltrán and Leykin [5, 6] give explicit tracking algorithms and distinguish arithmetic from bit complexity. We follow this separation, deriving the estimates for our smooth mass maps directly from their Jacobians and second derivatives. The polynomial-specific condition formulas are not assumed here.

We count arithmetic operations and evaluations of the one-dimensional functions $\Phi,\phi$ at unit cost. The bandwidth $\sigma$ is fixed during one continuation. Here $N=\sum_i n_i$ is the total number of points and $h=1/K$ is the continuation step.

Cost of one step. For each point, compute $u\cdot p-a$ and accumulate its contribution to the value and ambient derivative row in (34)–(35). Convert the accumulated rows to a tangent basis, then solve the linear systems for prediction and correction. Including the dimension explicitly, Algorithm (3) costs $O(Nd+d^3)$ per step: the first term comes from the point sums, the second from basis conversion and dense linear algebra. With our fixed-dimension convention this is $O(N)$, as are finding the closest points and checking the reconstructed plane.

Thus the cost is $O(NK)$ and is linear in $N$ for a fixed admissible step. For a family of inputs, the total tracking cost is uniformly $O(N)$ when $K$ is bounded independently of $N$. Distance error at most $\eta$ is obtained by

with work

In particular, with uniform geometric bounds independent of $N$ this is $O(N\eta^{-1/4})$ as $\eta\to0$.

Proof. Theorem 3.1 bounds the error at every corrected point by $C_0h^4$. Multiplying the step cost by $K=1/h$ proves (43). The choice (44) ensures both $h\le h_0$ and $C_0h^4\le\eta$; substitution gives the work bound.

This is an error estimate at the corrected nodes. In a chart, linear interpolation between successive nodes has coordinate error at most $QC_0h^4+Ch^2/8$, since $\lVert x''\rVert\le C$. Thus the chartwise interpolant has only $O(h^2)$ uniform error. The endpoint $t=1$ is a corrected node and has the $O(h^4)$ bound.

What determines an admissible step. To make the geometric dependence explicit, substitute (7) into (13). This gives

Indeed, the last two terms give $Q\sqrt{2C/r}$, which also dominates $D=2\kappa(1+V)$ because $2(1+V)\le\sqrt{8}\sqrt{1+V^2}$. The error constant is $C_0=(9/4)Q\kappa C^2$. These formulas separate the linear dependence on $N$ from the path’s conditioning, derivative bounds, and chart margins. Uniform bounds independent of $N$ give a linear-time family for fixed accuracy. Regularity alone does not give those uniform bounds.

Adaptive steps can avoid imposing the worst local step on the whole path. Here is an elementary integral bound. Let $s(t)>0$ be a continuous local step scale, and suppose the accepted steps have been justified, for example by (15). Assume, except for the final shortened step, that $\theta s(t_k)\le h_k\le s(t_k)$, where $0<\theta\le1$, and that $s(t)\le cs(t_k)$ on each accepted interval, with $c\ge1$. Then their number satisfies

Indeed, every nonfinal step contributes at least $h_k/(cs(t_k))\ge\theta/c$ to the integral; summing proves the bound. With bounded correction work per step this gives $O(N(1+(c/\theta)\mathcal{L}_s))$ tracking work. Unlike a global minimum-step bound, this integral charges a small local step only over the part of the path where it is needed. The estimate presupposes validated local steps and the stated variation bound; it does not replace their verification.

For the Gaussian homotopy the upper derivative bounds do not require an additional factor of $N$: the sums are normalized within each color. If all points and model centers have norm at most $R$, use $u(\xi)=(u_0+E\xi)/\sqrt{1+\lVert\xi\rVert^2}$ with orthonormal $E\perp u_0$. Differentiation gives $\lVert Du\rVert\leq1$, $\lVert D^2u\rVert\leq6$. Put

The chain rule and the bounds on $\phi,\phi'$ give $\lVert Df_{i,s}\rVert\leq A_s$ and $\lVert D^2f_{i,s}\rVert\leq H_s$. For unit-bandwidth Gaussian models and $F=(1-t)g+tf_\sigma$, we obtain $B=O(1)$ and $L=O(\max\{H_1,H_\sigma\}+A_1+A_\sigma)$, with constants independent of $N$. The mixed spatial–$t$ derivative has bound $A_1+A_\sigma$, and $F_{tt}=0$. On unit product vectors the two mixed coefficients have total absolute value at most $1$, proving the Hessian estimate. Consequently, with $R,\alpha^{-1},\rho^{-1},Q$ and $h_{\mathrm{ch}}^{-1}$ bounded, these formulas give $\Gamma=O(1+\sigma^{-2})$ for $0<\sigma\leq1$. If a regularizing perturbation is used, its derivatives must be included in these bounds.

Final accuracy and exact reconstruction. If only the endpoint needs higher accuracy, any admissible step can be kept fixed and additional Newton iterations used at $t=1$. By (5), residual $\delta$ requires at most $m=O(\log(1+\log^+(C_1/\delta)))$ additional iterations. The total work is then

and the intrinsic endpoint error is at most $2Q\delta/\alpha$. This refinement is optional in Corollary 5.6.

For an exact discrete cut, use the residual $1/(8n_{\max})$ and the bandwidth-halving procedure above. If $K_j,m_j$ are the continuation and refinement counts at scale $j$, its total arithmetic work is

Equation (42) bounds the number of reductions once the requested residuals are attained. Thus the work per pass remains linear in $N$, while the bandwidths and path constants must be accounted for separately. The uniform-step estimates count exactly the operations of (3); an adaptive implementation must also count rejected steps and extra correction iterations.

Evaluation accuracy. Adaptive precision for path tracking is studied by Bates, Hauenstein, Sommese, and Wampler [4]. To retain the $O(h^4)$ nodal error with inexact computation, it suffices to have velocity error $O(h)$, derivative error $O(h^2)$, and value or linear-solve residual error $O(h^4)$, with uniform constants and sufficiently small $h$. The predictor error is then $O(h^2)$, and each term of (17) is $O(h^4)$; induction preserves the bound. The cost of attaining these evaluation tolerances is additional to the unit-cost arithmetic model.

Distant points can be handled using side counts. Replacing $\Phi(s_p/\sigma)$ by its limiting side indicator and its derivative by zero for $\lvert s_p\rvert>T\sigma$ gives component errors at most $\Phi(-T)$ and $\sqrt{1+R^2}\Phi(T)/\sigma$, respectively. These follow by averaging the omitted tails, and can be made to meet the preceding tolerances. A direct scan still costs $O(N)$; only the normal-distribution evaluations are restricted to the narrow layer.

Smoothing does not supply a uniform conditioning bound. Even $\{-1,1\}\subset\mathbb{R}$ has median derivative $\lvert f_\sigma'(0)\rvert=\phi(1/\sigma)/\sigma$, exponentially small as $\sigma\to0$. Odd data avoid this particular endpoint effect by (40), but may still have poorly conditioned continuation paths. Uniform linear-time bounds therefore require uniform control of the path constants.

Remark 5.7 (Weights). Positive normalized weights can replace $1/n_i$ in the finite sums without changing their evaluation cost. The discrete limit proof still gives at most half of each color’s weight in either open half-space. For rational weights $w_{ip}=m_{ip}/W_i$, clearing denominators gives exact tests $\sum_{p\in H^\pm}m_{ip}\le\lfloor W_i/2\rfloor$; coincident replication of atoms is unnecessary. The regularity and reconstruction theorems above concern equally weighted odd sets in general position.

Finding multiple solutions

We now vary the starting model while keeping the target problem fixed. The questions are which solutions become reachable and when a search through the model parameters can stop.

Assume throughout this section that the target zeros are regular. There are then finitely many zero orbits. The quotient zero set of a regular homotopy consists of circles and intervals. Only one interval meets the unique initial orbit; every other target endpoint is paired with another target endpoint. Following the selected arc, even through its folds, cannot reach those other components.

Changing the model

We begin with the stability of the selected answer under small changes of the model, then prove reachability for ham-sandwich cuts.

In a smooth family of regular homotopies with a fixed regular target, the selected endpoint is locally constant. For a smooth family this can be seen directly. Along a compact parameter path $p(s)$, the total zero set modulo $G$ projects submersively to $s$, because $D_{(x,t)}F$ is onto. At the horizontal boundaries, invertibility of $D_xF$ gives lifts of $\partial_s$ tangent to those boundaries. A partition of unity combines these lifts; compactness makes their flow identify the zero curves. On the target boundary the spatial component is zero, since the target is fixed and regular. The initial endpoint therefore remains paired with the same target. Thus endpoint changes require a singularity of the full homotopy or a boundary degeneracy; spatial folds alone do not change the pairing.

Proof. At $p_0$ the branch is constant, $x(t)=q$. Compactness gives a uniform inverse bound for (50). The implicit function theorem gives nearby graphs for all $t$; uniqueness glues them on overlaps. At $t=0$ the graph is the model zero near $q$, and at $t=1$ it is the fixed zero $q$.

Proof. Fix a regular target bisector $H$ and choose its section centroids $c_i$ as the Gaussian centers. By (25), they are affinely independent, so this model has $H$ as its unique zero orbit. In unit-normal tangent coordinates let $C_H$ have rows $(-1, c_i^T E)$. Then $Df(H) = \operatorname{diag}(m_i)C_H$ and $Dg(H) = \phi(0)C_H$. Their pencil is

which is invertible for every $t$. Apply Proposition 6.1.

The centroid choice proves existence of successful model parameters; it is not an efficient procedure for finding an unknown cut. One possible search interleaves a dense sequence of starts with increasing finite computation budgets and decreasing step sizes. Every regular cut can then be approximated to any prescribed accuracy: each has an open neighborhood with a common positive admissible step. Interleaving prevents a singular run from blocking later starts. A finite stopping rule additionally needs a known solution count or quantitative bounds on successful neighborhoods. The theorem concerns the full family of Gaussian centers. It does not prove that every prescribed family of orthogonal projections, parametrized only by their kernel lines, reaches every target zero.

Related approaches include continuation and monodromy for polynomial systems [8], real monodromy [12], and deflation to remove already known roots [10]. Their completeness conditions are different. Here we explore the parameters of a model while keeping the target fixed.

Finite parameter regions

A finite search is possible when the parameter space splits into finitely many regions with constant answers. Piecewise-linear maps allow us to describe such regions by finite systems of inequalities.

Let $K$ be a fixed finite equivariant triangulation of the cylinder over a closed free $G$-PL $n$-manifold, with both boundary slices as subcomplexes. On a compact semialgebraic parameter space $P$, prescribe continuous semialgebraic vertex values $a_v(p) \in V$, equivariantly in $v$, and extend affinely on each simplex. Denote the resulting homotopy by $F_p$. Assume a unique initial zero orbit for every $p$ and a fixed target whose zeros avoid its $(n-1)$-skeleton. Define

Proof. A zero on a face $[v_0,\ldots,v_k]$, $k<n$, is equivalent to the feasibility of

Semialgebraic projection and a finite union show that $\Delta_K$ is semialgebraic. Compactness of the barycentric simplex shows it is closed. Its complement has finitely many semialgebraic components.

For $p \in U$, a zero on an $n$-face is interior and nonsingular, by the barycentric argument in Proposition 2.5. Its positive coordinates persist under small parameter changes. A face with a zero has positive distance of its image from zero, which also persists. Thus the list of zero-containing faces is locally constant. Each top simplex joins precisely its two zero-containing faces, so the entire zero-segment incidence graph and its quotient are locally constant. The fixed target marks and the unique initial mark then select the same endpoint. Each $B_i$ is a finite union of components of $U$; its boundary cannot meet $U$. The stratification and dimension assertions are the standard relative-boundary properties of open semialgebraic subsets of a manifold.

These walls depend on the triangulation and can be artificial; the same endpoint may persist across them. No claim that $\Delta_K$ has empty interior is needed. The convex-hull feasibility condition above is the exact test for a wall. For a general semialgebraic parameter space, retain a finite stratification and interpret the geometry on its strata, including their lower-dimensional incidences.

For a jointly PL equivariant map on finite polyhedra, intersect the total simplices with $F=0$ and subdivide $P$ compatibly with the projections $\pi(E)$ of all faces of the quotient zero complex. The relative interior of $E$ meets a fiber exactly when $p\in\operatorname{relint}\pi(E)$; its dimension is $\dim E-\dim\pi(E)$. These tests and the face inclusions give constant fiber incidences on each open parameter cell, including the boundary marks. General semialgebraic families admit a finite partition by Hardt’s theorem [11]. Being PL in $x$ for each $p$ alone does not imply joint PL dependence.

Region growing

Start at a model parameter, determine its endpoint, and grow an explored neighborhood through its frontier. When the component is exhausted, restart in the unexplored part. This region-growing search (informally, the rodent method) is flood fill with restarts, using breadth-first or depth-first search [24]. It performs connected-component labeling; Hoshen–Kopelman labeling [14] is another classical implementation of that task. Boundary following alone does not exhaust interiors or discover separate components. Covering by overlapping neighborhoods is also the geometric idea of Henderson’s multiple-parameter continuation [13].

Proof. In the barycentric subdivision, discard coordinates corresponding to simplices of $D$ and renormalize the rest. Their sum is positive on $U$. The straight homotopy stays in the same simplex and outside $\Delta$, giving a deformation retraction onto the full subcomplex of the remaining barycenters. Its one-skeleton is the stated graph, so its components are exactly those of $U$. One continuation from a relative-interior point of a seed simplex labels its whole component. Search visits each vertex and adjacency list once; restarting exhausts the graph. Duplicate endpoint labels are merged in the answer list.

A semialgebraic triangulation compatible with $\Delta_K$ provides this hypothesis for Theorem 6.3. If labeling the $j$th component costs $T_j$, including continuation and endpoint identification, the total after the graph is constructed is

Several components may carry the same label; no connectedness assumption on their union is used. To obtain all target zeros, every target must additionally be reachable in the chosen parameter domain.

For adaptive exploration one can justify neighborhoods directly. Along a known monotone branch $x_0(t)$ at $p_0$, put $J_0(t) = D_xF(x_0(t),t,p_0)$. Suppose $\lVert J_0(t)^{-1}\rVert\le\alpha^{-1}$ and, for $\lVert y-x_0(t)\rVert\le\rho$, $\lVert p-p_0\rVert\le r$,

If $L_x\rho+L_pr\le\alpha/2$ and $Ar\le\alpha\rho/2$, then $y\mapsto y-J_0(t)^{-1}F(y,t,p)$ is a contraction of the closed radius-$\rho$ ball into itself. Its unique fixed points give regular monotone branches. For a fixed target their endpoint is the same zero. Smaller overlapping tubes handle several charts; at folds one uses the augmented system (22).

Agreeing labels at finitely many samples do not justify labeling an entire cell. Near walls the validated neighborhoods may shrink without a finite stopping time. Finite exhaustion therefore uses a compatible decomposition or an explicit resolution assumption: if every label contains a parameter ball of radius $r_* > 0$, any net of covering radius less than $r_*$ meets every label. In a bounded $r$-dimensional parameter chart a regular mesh has $O(h^{-r})$ cells, making this approach most suitable for small parameter dimension. Projective chart seams must use the prescribed identifications.

Figure 3 illustrates why the search should allow disconnected regions for one solution. Two separated green parts of the computed parameter diagram select the same common bisector of two nonsymmetric polygonal sets. The diagram is numerical evidence of disconnectedness, rather than a proof excluding arbitrarily thin connections.

Acknowledgments. The author thanks Roman Karasev and Alexey Fakhrutdinov for helpful comments and discussions.

AI use statement. LLMs were used for proof refinement, literature review, and manuscript revision.

The University of Texas Rio Grande Valley, Brownsville, Texas, USA

[email protected]