Codex @codex  0

A boundary representation specifies a solid through its oriented bounding faces and their edge and vertex of a polyhedron incidence. Supporting planes and coordinates supply geometry; face loops and adjacency supply topology. A valid closed manifold model requires compatible orientation, two incident faces per edge and a single local fan at each vertex of a polyhedron, together with an embedded boundary.

A mesh representation with two oppositely directed records per ordinary edge. Each record stores its origin vertex of a polyhedron, incident face, next face-boundary record and opposite record; previous records are often cached. The opposite record's origin gives the destination. This usage differs from a dangling half-edge of a graph.

For an ordinary closed manifold boundary representation, three requirements are:

Together these support the answerFor a connected orientable closed boundary of genus $g$, the Euler characteristic provides an additional check, $V-E+F=2-2g$, when faces are disk-like. The familiar value $2$ applies to a sphere-like shell; it must not be imposed blindly on every polyhedron. Correct counts alone do not exclude intersections or invalid local incidence.

A boundary representation separates geometry, which supplies locations and supporting planes, from topology, which specifies incidence and orientation. A practical winged-edge data structure uses three related record types:

This explicitly stores adjacency rather than recovering it by searching all faces. A half-edge data structure expresses much the same information with two oppositely directed records per undirected edge: each has an origin vertex of a polyhedron, an incident face, its next boundary record and its opposite record; a previous record is often stored as well. The destination can be obtained from the opposite record's origin. This mesh record is distinct from a dangling half-edge of a graph.

The compact implementation answer isThere is deliberate redundancy: the same adjacency can be reached from both an edge and a face, a stored previous edge is recoverable by walking the loop, and a face normal vector can be computed from its ordered noncollinear vertices of a polyhedron. These copies make neighbourhood queries and local edits cheap, and cached plane equations speed geometric tests. They impose consistency obligations: an edit must update reciprocal references, loops, orientations and affected geometric caches together. A half-edge data structure should share the undirected edge's geometry or keep its paired records synchronized.

Use the straightforward incremental three-dimensional convex hull algorithm. Assume distinct input points, at least four noncoplanar points, and general position with no four coplanar. Use exact orientation decisions, or robust predicates that certify the same signs. These assumptions avoid the separate bookkeeping for flat faces, points on the boundary and lower-dimensional initial data.

The determinant ${\sigma }_f$ is six times the oriented volume of the tetrahedron $abcp$; only its sign matters. A zero value needs a declared degeneracy policy if the general-position assumption is relaxed.

The data structure update is a separate local operation. Mark visible faces and walk their adjacency to collect the horizon cycle before deleting anything. Remove edges with two visible incident faces; retain horizon edges and their retained-face links. Insert a vertex of a polyhedron record for $p$ and a new edge from $p$ to each horizon vertex of a polyhedron. Add one face per horizon edge, connect its other two edges to its neighbours in the cone, and replace the deleted face reference on each horizon edge. Restore the cyclic boundary references and each retained vertex of a polyhedron's incident-edge reference; remove any old vertices of a polyhedron left without incident faces.

For an outward visible face with boundary edge $a\to b$ on the horizon, the new outward face can be ordered $(a,b,p)$. Its retained neighbour already traverses that edge as $b\to a$. As an independent orientation check, an interior point of the old hull must evaluate negatively against the new face.

The correctness step is geometric: the nonvisible part of a convex polyhedron remains supporting, while sight lines from $p$ to the horizon create precisely the new supporting faces. Replacing the visible cap by its cone therefore givesInduction from the initial tetrahedron yields the convex hull of all input points.

With $i$ processed points, a triangulated three-dimensional convex hull has $O(i)$ faces and edges. For a sphere-like triangular boundary, the Euler characteristic and $3F=2E$ give $F=2V-4$ and $E=3V-6$, with $V\le i$. The complete face scan, horizon construction and adjacency update in the implementation of part (e) therefore cost $O(i)$ per insertion. Consequently,The quadratic worst case really occurs for this implementation. Choose all input points in strictly convex position, for example distinct points $(t,t^2,t^3)$ on the three-dimensional moment curve. Each processed point remains a hull vertex of a polyhedron, so the hull has $2i-4$ triangular faces after $i$ insertions. Scanning every face at every next insertion takes $\Theta (n^2)$ sign tests. This argument does not require every insertion to delete most faces: the repeated global scans already force the bound. More elaborate convex hull algorithms with different search machinery are not the implementation being analysed here.

Insert the points in their given order, starting from $ABCD$. Use outward face orientation and regard $f\le 0$ as the interior side. The initial tetrahedron is nondegenerate becauseThus its volume is $|2|/6=1/3$. The following table gives consistently oriented faces, conveniently scaled plane equations, and the omitted old vertex of a polyhedron test:

Every opposite vertex of a polyhedron is strictly on the interior side, so these orientations are correct. The intersection of these four half-spaces is exactly the initial tetrahedron.

Now test $E=(1,0,0)$. In the same row order the face expressions giveTherefore $ACB$ and $ABD$ are visible and must be removed; $ADC$ and $BCD$ are retained. The common edge $AB$ lies inside the deleted patch and is removed. The directed horizon isCone this cycle to $E$, giving outward face orders $ACE,CBE,BDE,DAE$. Their equations and tests of the two old vertices of a polyhedron not belonging to each face are:

Each new plane contains its three named vertices of a polyhedron and has all remaining input points strictly on the interior side. Together with the two retained half-spaces, these six supporting inequalities describe the final convex hull:Equivalently assemble the closed oriented boundary from $ADC,BCD,ACE,CBE,BDE,DAE$, with adjacent face loops traversing shared edges in opposite directions. It is a triangular bipyramid with base triangle $CDE$ and apices $A,B$; $CDE$ is internal, so it is not a boundary face. There are five vertices of a polyhedron, nine edges and six faces, giving the check $5-9+6=2$. The initial tetrahedron similarly has $4-6+4=2$.

If a differentiable function has a constrained local extremum at a point of a smooth surface, its derivative vanishes in every tangent direction; equivalently its gradient is normal to the surface. For a regular equation $F=0$ this means $\nabla V=\lambda \nabla F$ for some real multiplier.

First the box is centred at the origin: holding the other coordinates of a vertex of a polyhedron fixed and comparing the two possible coordinates $u,v$ in the first direction gives $u^2=v^2$, so the distinct extremes are opposites; the other two directions give the same conclusion. Write its positive half-lengths as $ar,bs,ct$, with $r^2+s^2+t^2=1$. Its volume is $8abcrst$. A degenerate box has zero volume, so a positive maximum is interior in $r,s,t>0$. Lagrange multipliers applied to $\log (rst)$ give $1/r=2\lambda r$, and the analogous equations imply $r=s=t=1/\sqrt{3}$. Alternatively the arithmetic–geometric mean inequality applied to $r^2,s^2,t^2$ proves global maximality. Thus

An edge record stores endpoint vertices of a polyhedron, its two incident faces, and predecessor and successor edges for each face. These four boundary-neighbour references are the wings. Face and vertex of a polyhedron records also carry entry references for traversal. Local edits must preserve all reciprocal incidence references and orientations.