Height geometry and weak-membership binary search

Compactness of $K$ makes each nonempty vertical section compact, so its minimum exists; projection makes $C$ compact and convex. Convex combinations of two minimizing boundary points show convexity of $h$. For $\mathrm{\parallel }y\mathrm{\parallel }\le r$, the inner ball supplies a point at height zero, while the outer ball bounds all heights below by $-R$. Thus $-R\le h(y)\le 0$ on that ball.

More generally on $B(0,d)$, $0<d<r$, let $y,y^{\mathrm{\prime }}$ be distinct and extend the directed line from $y$ through $y^{\mathrm{\prime }}$ by $r-d$ to $p=y^{\mathrm{\prime }}+(r-d)(y^{\mathrm{\prime }}-y)\mathrm{/}\mathrm{\parallel }{y}^{\mathrm{\prime }}-y\mathrm{\parallel }$. Then $p\in B(0,r)$ and convexity on the segment $[y,p]$ gives $h(y^{\mathrm{\prime }})-h(y)\le R\mathrm{\parallel }{y}^{\mathrm{\prime }}-y\mathrm{\parallel }\mathrm{/}(r-d)$. Exchange $y,y^{\mathrm{\prime }}$ and put $d=r\mathrm{/}2$ to obtain the Lipschitz claim.

The ball $B((y,0),r\mathrm{/}2)$ lies in $K$. Its convex hull with $(y,h(y))$ contains a ball of radius $\theta r\mathrm{/}2$ about $(y,(1-\theta )h(y))$ for every $0\le \theta \le 1$: combine the vertex with every point of that ball. Consequently all heights between $h(y)(1-2\epsilon \mathrm{/}r)$ and $-r\mathrm{/}2$ lie in the inward $\epsilon$-erosion, whenever this interval is nonempty. If $\epsilon \ge r\mathrm{/}2$ the claimed OUT bound is automatic from $h(y)\ge -R$ and $t\le -r\mathrm{/}2$. For $0<\epsilon <r\mathrm{/}2$, write $H=-h(y)\le R$. If the interval is empty, then $H(1-2\epsilon \mathrm{/}r)<r\mathrm{/}2$, so $H-r\mathrm{/}2<2H\epsilon \mathrm{/}r\le 2R\epsilon \mathrm{/}r$; every $t\le -r\mathrm{/}2$ therefore satisfies $t<h(y)+2R\epsilon \mathrm{/}r$. If the interval is nonempty, OUT excludes its heights, so $t\le h(y)(1-2\epsilon \mathrm{/}r)\le h(y)+2R\epsilon \mathrm{/}r$. This uses an inclusion of balls, not an incorrect identity for the erosion of a cone.

For completeness, subgradients here need no arbitrary selection. The truncated epigraph $E=\{(y,t):y\in C,h(y)\le t\le R+1\}$ is compact and convex: it is the image of the compact set of pairs consisting of a point of $K$ and a permitted upward vertical displacement. Fix interior $y$ and $p=(y,h(y))$. Let $p_j=p-e_n\mathrm{/}j$, and let $q_j$ be its unique nearest point in $E$ by [F2]. Minimality along a segment gives $⟨q_j-p_j,w-q_j⟩\ge 0$ for all $w\in E$, by expanding squared distance and taking the right derivative at zero. Moreover $\mathrm{\parallel }{q}_j-p\mathrm{\parallel }\le 2\mathrm{/}j$. A subsequence of the unit normals $(q_j-p_j)\mathrm{/}\mathrm{\parallel }{q}_j-p_j\mathrm{\parallel }$ converges by [F3] to a unit normal $(u,t)$ with $⟨(u,t),w-p⟩\ge 0$ on $E$. Upward vertical segments imply $t\ge 0$; if $t=0$, interior displacements of $y$ in both horizontal directions force $u=0$, a contradiction. Thus $t>0$ and $-u\mathrm{/}t$ is a subgradient of $h$ on $C$. At a point where the Lipschitz bound holds on a neighborhood, applying the subgradient inequality in the directions $\pm p\mathrm{/}\mathrm{\parallel }p\mathrm{\parallel }$ gives $\mathrm{\parallel }p\mathrm{\parallel }\le L$.

Fix $\mathrm{\parallel }y\mathrm{\parallel }\le r\mathrm{/}2$. A subgradient $p$ of norm at most $2R\mathrm{/}r$ gives the supporting inequality $⟨(-p,1),(z,t^{\mathrm{\prime }})-(y,h(y))⟩\ge 0$ on $K$. If $(y,t)$ is within $\epsilon$ of $K$, Cauchy–Schwarz gives $t\ge h(y)-\epsilon \mathrm{\parallel }(-p,1)\mathrm{\parallel }\ge h(y)-3R\epsilon \mathrm{/}r$. This proves the IN implication, also at the transverse-ball boundary by the bound from step 2.1 on slightly larger balls and passage to its limit.

Maintain endpoints $\mathrm{\ell },u$. Initially $\mathrm{\ell }=-R\le h(y)+2\delta \mathrm{/}3$ and $u=-r\mathrm{/}2\ge h(y)-\delta$. An IN answer replaces $u$ by the midpoint and preserves its lower bound by step 4.1; OUT replaces $\mathrm{\ell }$ and preserves its upper bound by step 2.2. When $u-\mathrm{\ell }\le \delta \mathrm{/}3$, these invariants give $h(y)-\delta \le u\le h(y)+\delta$. Each iteration halves the bracket, proving the logarithmic query count. Fixed finite arithmetic and the deterministic oracle completion make the whole binary-search transcript a function of the input label. Store its transcript, copy its output, and reverse its computation and oracle calls; this implements that value oracle with clean work and only a constant factor more queries.

Write $z=(y,t)\in K$. Evaluating the approximate-subgradient premise at $y=0$ gives $b\ge 0$. Since $a\ge 0$ and $\mathrm{\parallel }y\mathrm{\parallel }\le R$, that inequality gives $⟨(-v,1),z⟩=t-⟨v,y⟩\ge h(0)-aR-b$. At $x=(0,-\mathrm{\parallel }x\mathrm{\parallel })$ the OUT implication gives $h(0)\ge -\mathrm{\parallel }x\mathrm{\parallel }-2R\epsilon \mathrm{/}r$; if its height is below $-R$, this inequality follows directly from $h(0)\ge -R$. If $\mathrm{\parallel }x\mathrm{\parallel }<r\mathrm{/}2$, an OUT answer requires $\epsilon \ge r\mathrm{/}2$ by the inner ball, and the same inequality again follows from $h(0)\ge -R$. Divide by $\mathrm{\parallel }(-v,1)\mathrm{\parallel }\ge 1$ to obtain the stated separation inequality.