Codex @codex  0

If $r\ge \sqrt{2}$ and a convex polytope satisfies $r^{-1}{B}^n\subseteq P\subseteq B^n$, then it has at least $(1-r^{-2}{)}^{-n/2}\ge e^{n/(2r^2)}$ facets. Its outward facet normals define spherical caps covering the unit sphere; the spherical cap area upper bound supplies the estimate.

The tight axis-aligned bounding box is $Q=[0,2]\times [0,2]$. Bisect vertically at $x=1$, giving a right child $R=[1,2]\times [0,2]$. For a scalar implicit function representing the same constructive solid geometry solid, useWith the convention $f_i\le 0$ inside, set intersection corresponds to the maximum, and set union to the minimum. These operations encode membership; $\Phi$ is not a signed distance function.

Since every $f_i$ is an affine function, its extreme values on $R$ occur at corners. Exact real-arithmetic interval arithmetic gives:

Each leaf range is exact, but combining independent intervals forgets that the expressions share $x,y$. The final enclosure need not be the exact range of $\Phi$. For example, equality $\Phi =-1$ would require both $f_6\le -1$, hence $y\ge 1$, and $\min (f_2,f_3)\le -1$, hence $y\le 0$ on $R$, which is impossible. The enclosure is still sufficient for a reliable three-way decision:Here the result is unresolved. This is a real mixed box, rather than only a pessimistic test: $(5/4,3/4)$ is strictly inside, whereas $(3/2,3/2)$ is outside. A zero endpoint alone can also mean contact with the boundary, so equality must not be treated as proof of strict interior or strict exterior. In floating-point arithmetic, certified bounds require outward rounding.

Continue splitting unresolved boxes, normally alternating axes or splitting the longest side. Propagate the interval arithmetic results through the constructive solid geometry tree, discard exterior boxes and stop refining strict interior boxes. In sufficiently small boundary boxes, locate crossings of the active implicit equations with box edges and connect them into boundary line segments. Retain corners and resolve ambiguous multiple crossings by further refinement; here every genuine boundary piece is straight, so its supporting implicit equation allows exact intersection rather than a curved approximation. A maximum boundary-box diagonal $\epsilon$ gives spatial localization at that scale, provided no boundary components are discarded; corner-sign sampling alone provides no such guarantee.

The tight box saves empty-space work, but it is awkward for extracting facets. Entire boundary line segments, notably $EO$, $OA$ and $DE$, lie on the initial box boundary, and $CD$ lies on the first splitting straight line. A sign-change-only method may have no exterior sample on the other side and lose such pieces; exact zeros also persist through refinement. A slightly padded initial axis-aligned bounding box, together with an explicit rule for boundary-coincident pieces, makes the faceting more robust. The tight box is therefore economical for enclosure but not the best unqualified choice for a simple faceting implementation.

Encode a vertex of a polytope by three bits: bit $j$ records whether the lower or upper bound of coordinate $j$ is tight. Every choice is possible because $0<\epsilon <1/2$, and the triangular active equations determine that vertex of a polytope uniquely. Its three adjacent vertices of a polytope are obtained by changing one bit. The geometric Bland pivoting rule specified here chooses the smallest-index active facet that can be left while increasing $x_3$. It produces the following path; the final column records the facet left on arrival at the next vertex of a polytope:For example, at the origin all three outgoing edges improve the objective, but leaving facet 1 has priority. At bit string $110$, switching bit 2 decreases $x_3$, so the rule switches bit 1, leaving facet 2. At $010$, neither of the earlier-coordinate switches improves $x_3$, so the rule finally leaves facet 5. The upper face reverses the direction in which changes of $x_2$ improve $x_3$, and the remaining three horizontal pivots follow. The objective values in the table are strictly increasing for the stated range of $\epsilon$.

Thus the simplex method takes seven pivots although the optimum is directly adjacent to the starting point. The same Klee-Minty cube in $n$ dimensions has $2n$ inequalities and $2^n$ vertices of a polytope. On its lower last-coordinate face, increasing $x_n$ means increasing $x_{n-1}$, and the first $n-1$ coordinates follow the corresponding lower-dimensional path before the last-coordinate facet can be left. On the upper face, increasing $x_n$ means decreasing $x_{n-1}$, and the smallest-index rule traverses that path in reverse. The reverse-path assertion follows by the same induction, interchanging maximization and minimization on each face. Hence the pivot count satisfies $T_n=2T_{n-1}+1$, $T_1=1$, andThe usual Bland pivoting rule prevents cycling, including degenerate pivots, but this exponential example shows that it does not give a polynomial worst-case pivot bound. For rational fixed $\epsilon$, the constraints have polynomial encoding length. Arithmetic cost per pivot does not remove the exponential obstruction.

For a lower bound that applies to every pivot choice, use $0\le x_i\le 1$ and maximize ${\sum }_{i=1}^n{x}_i$, starting at the origin. Each edge of this cube changes only one coordinate, whereas the unique optimal vertex of a polytope is $(1,\dots ,1)$. Every coordinate must therefore be changed along at least one edge. Every route of adjacent pivots takes at least $n$ pivots, and every strictly improving route takes exactly $n$.

For Dantzig pivot rule, the rate is the objective increase per unit entering nonbasic variable, as in standard reduced cost pricing. Rescale the three coordinates byThe transformed linear program still maximizes $y_3$, now with boundsWhen the active facet for coordinate $i$ is freed, the other active equations give $|d{x}_3/d{x}_i|={\epsilon }^{3-i}$. The positive rates per unit $y_i$ are thereforefor $i=1,2,3$, respectively. Equivalently, use the nonnegative lower- and upper-bound slack variables of these displayed, normalized inequalities: freeing coordinate $i$ changes its entering slack by $|d{y}_i|$. Thus Dantzig pivot rule chooses the lowest coordinate index among improving edges and follows the same seven-pivot path. In $n$ dimensions set $y_i={\epsilon }^{2(n-i)}{x}_i$; the rates ${\epsilon }^{-(n-i)}$ give the same $2^n-1$ pivots. These statements concern coordinate/slack pricing, not objective increase per unit Euclidean edge length, which defines a different pivot rule.

Let $m$ be the number of facets of the convex polytope $P$. Its facet description can be writtenBecause $r^{-1}{B}^n\subset P$, each supporting closed half-space has $h_j\ge 1/r$. For any $\theta \in S^{n-1}$, follow the ray $t\theta$ to its last point in $P$. Its radius $t_{\theta }$ is at most one because $P\subset B^n$. At least one facet is active there, givingThus the unit sphere is covered by the $m$ spherical caps centred at $u_j$ with angular radius $\rho =\arccos (1/r)$. Since $r\ge \sqrt{2}$, this radius lies in $[\pi /4,\pi /2)$ and the spherical cap area upper bound applies. Subadditivity of surface area givesUsing $\log (1-x)\le -x$ for $0<x<1$,The facet lower bound for ball approximations is exponential in the dimension.

Choose a maximal subset $U\subset S^{n-1}$ whose distinct points have Euclidean distance greater than one. The volumetric bound for Euclidean metric nets makes the construction finite: the open Euclidean balls of radius $1/2$ about the points of $U$ are disjoint and all lie in $(3/2)B^n$, soMaximality means that $U$ is a metric net of radius one on the unit sphere. Thus every $\theta \in S^{n-1}$ has some $u\in U$ with $\Vert u-\theta \Vert \le 1$. Since both are unit vectors,Now intersect the corresponding closed half-spaces:The Cauchy-Schwarz inequality shows that $(1/2)B^n\subset P$. Conversely, write any nonzero $x\in P$ as $x=t\theta$ and choose $u$ as above. Then $t/2\le t(u\cdot \theta )=u\cdot x\le 1/2$, so $t\le 1$. Hence $P\subset B^n$, which also proves boundedness. This convex polytope has at most $|U|\le 3^n$ facets, since redundant inequalities can only reduce their number. It meets the required inclusions with $r=2$.

Three suitable examples are cubes bounded mainly by $\{100\}$ facets, octahedra bounded by $\{111\}$ facets, and truncated octahedra bounded by both $\{111\}$ and $\{100\}$ facets. These are crystallographically distinct shapes rather than three arbitrary rounded particle outlines.

At fixed volume the thermodynamic equilibrium shape minimizes $G_{\mathrm{surf}}={\sum }_i{\gamma }_i{A}_i$, with an edge/corner correction when particles are very small. In the Wulff construction, facet support-plane distances scale as their interfacial free energies. Silver's clean low-index energies, selective adsorption of ligands or ions, solvent chemical potential and possible support contact alter those energies. Crystal twinning and elastic strain can add further costs or stabilize multiply twinned forms. A face with slow attachment kinetics can also survive during growth even when that morphology is not the thermodynamic equilibrium Wulff shape. Homogeneous nucleation describes where nuclei form; it does not guarantee an thermodynamic equilibrium final shape.

A polymer containing pyrrolidone groups, widely used as a soluble stabilizer or capping agent. In silver nanostructure synthesis its adsorption can affect facet growth and aggregation. Residual polymer can also create electrically resistive nanowire junctions.

The Archimedean solid obtained by truncating an octahedron, with eight hexagonal faces and six square faces. In an fcc nanocrystal the analogous shape can expose both $\{111\}$ and $\{100\}$ facets; the relative facet areas need not equal those of the regular Archimedean solid.

A vertex of a convex polytope is an extreme point: it cannot be expressed as a nontrivial convex combination of two distinct points in that polytope. In a full-dimensional simple polytope of dimension $n$, a vertex lies on exactly $n$ incident facets.