Use the shortest path distances in the directed dependency graph to defineThe additional $1$ counts the final use of a positive unit Horn clause, which corresponds to a fact rather than an edge of $G$.

To justify the new lower bound, consider any complete proof from $R$ and fix $\neg p\in R$. At some step this obligation must be removed using a Horn clause with head $p$. If that Horn clause is the fact $\{p\}$, we have already found a dependency graph path of length zero ending at a fact. Otherwise select one negative body Boolean literal $\neg q$. Immediately after the step it belongs to the query, whether newly inserted or merged with an existing obligation. It must subsequently be removed. Record the edge $p\to q$ and repeat this argument at its later removal.

The selected removal times strictly increase. Since the proof is finite and ends with no obligations, this chain eventually uses a fact. A proof of $\ell$ actions therefore produces a dependency walk of at most $\ell -1$ edges from $p$ to a fact. Removing any cycles from that walk gives $d_G(p)\le \ell -1$. Hence $1+d_G(p)\le \ell$ for every initial obligation. If $d_G(p)=\infty$, no such proof exists. Combining this bound with the admissible heuristic $|R|$ by taking their maximum preserves admissibility.

For a strict improvement, useHere $d_G(p)=2$, so $h_1(R)=1$ while $h_2(R)=3$. The three successive obligations are $\neg p,\neg q,\neg r$, followed by the empty query, so the improved bound is exact.

Do not sum all the values $1+d_G(p)$ without an additional argument: different obligations may share work. For example, with $T=\{\{p,\neg r\},\{q,\neg r\},\{r\}\}$, the query $\{\neg p,\neg q\}$ takes three actions, while that sum would be four.

Yes: $h_1(R)=|R|$ is an admissible heuristic. One application of the resolution inference rule removes just one current negative Boolean literal. It may add other negative Boolean literals, and some of those may already occur, but it cannot remove any other current obligation. ConsequentlyIf $\ell$ actions lead from $R$ to $\varnothing$, applying this inequality at every step gives $0\ge |R|-\ell$. ThusIt is also a consistent heuristic, since $h_1(R)\le 1+h_1(R^{\prime })$ and $h_1(\varnothing )=0$. In particular, merging duplicate obligations cannot invalidate the lower bound: removing several duplicates from the representation never counts as removing several distinct members of a set.

Termination is not guaranteed. TakeBoth members of $T$ are valid Horn clauses with distinct underlying Boolean variables. The only possible continuation alternatesThe empty query is unreachable. With the admissible heuristic $h=0$, ordinary A-star search keeps generating the next search node forever, despite there being only two reachable states.

A modification requiring no additional stored state collection is to impose the known search depth boundThe unit-cost $g$ already stored by A-star search is also its search depth; the bound is a scalar computed from the input, not a closed set. Apply the goal test before refusing expansion at the bound.

To prove completeness of this modification, remove any segment between two equal states in a successful proof. The successor choices after the later occurrence are available at the earlier occurrence because the search transition model depends only on the current query. Repeating this removal gives a proof with no repeated states, hence at most $2^N-1$ actions. In particular, a shortest proof never needs a repeated state, since every removed segment has positive cost. The depth restriction therefore preserves a shortest proof whenever one exists.

The restricted search tree has finite depth and finite branching factor, so it is finite. A-star search must then either remove a goal or exhaust the search frontier and report failure. Its existing search frontier may still be large; the modification saves a separate visited-state collection, not all storage used by tree search.

A-star search is best-first search with priorityHere $u$ is a search node, $s(u)$ is its state, $g(u)$ is its accumulated path cost, and $h^{\ast }(s)$ is the minimum remaining cost to any goal state, interpreted as $\infty$ if no goal is reachable. The inequality defines an admissible heuristic. Thus $f(u)$ is a lower bound on the cost of any solution extending that particular action history.

Initialize the search frontier with the root. Repeatedly remove a search node of least $f$, apply the goal test, and, if it is not a goal, insert its applicable-action children with their updated $g$ and $f$. In tree search, different action histories remain distinct search nodes even when they reach the same state; there is no global visited-state set.

For the finite branching factor and unit costs here, an admissible heuristic ensures that any first goal removed is optimal. If a cheaper solution existed, the search frontier would contain an unexpanded prefix of it with $f$ at most that cheaper cost, contradicting selection of the more expensive goal. Nonnegative $h$ also means only finitely many search nodes can have $f$ below any fixed finite cost, so a finite solution will eventually be reached. This does not guarantee termination when no proof exists.

Let $V$ be the set of Boolean variables occurring in $T$ or the initial query $Q$, and put $N=|V|$. Represent a current query by a subset $R\subseteq \{\neg p:p\in V\}$: the Boolean literals in this set are the outstanding obligations. The initial state is $R=Q$, and the goal test is $R=\varnothing$.

An action chooses a Horn clause $C\in T$ with positive Boolean literal $p$, provided $\neg p\in R$. Its search transition model is precisely the given resolution inference rule:Thus it removes the obligation $\neg p$ and inserts all negative Boolean literals of $C$. Repeated Boolean literals merge because queries are sets. A Horn clause without a positive Boolean literal supplies no action under the rule specified in this paper; it must not be treated as an additional way of finishing the query.

Give every action unit cost. A graph path with $\ell$ actions gives a proof containing $\ell +1$ queries, so minimizing either quantity gives the same shortest proof. Uniform-cost search orders the search frontier by the number of actions already taken and applies the goal test when removing a search node for expansion. Recording parent actions reconstructs the proof.

There are at most two choices, present or absent, for each of the $N$ negative Boolean literals. ThereforeThis bounds the state space, including the empty query, rather than the possibly infinite search tree of action histories.^[ref]

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$.

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.

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.

For a finite nonempty collection $X=\{p_1,\dots ,p_n\}\subset {\mathbb{R}}^3$, its convex hull is the smallest convex set containing all the points. Equivalently, it is the set of all convex combinations:Every convex set containing the $p_i$ must contain these combinations; the displayed set is itself convex and contains each $p_i$, proving the equivalence. For a full-dimensional finite collection this is a convex polyhedron. A collinear or coplanar collection instead has a lower-dimensional convex hull, so the solid case needs a separate dimensionality assumption.

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.

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.

For solid modelling, a polyhedron is a solid whose boundary consists of finitely many planar polygons, called faces, meeting along straight edges and at vertices of a polyhedron. A face is not merely a list of arbitrary spatial points: its boundary must lie in one plane and bound a valid planar region. The boundary is closed and consistently oriented so that inside and outside are defined.

For example, a tetrahedron has four triangular faces, six edges and four vertices of a polyhedron. A more general polyhedron need not be convex and can have handles or cavities. The concise definition is

The join has matching positions and first derivatives:Because both pieces have unit parameter intervals, these are also the one-sided derivatives of $S$ at $u=1$. Thus $S$ has first-order parametric continuity, and hence first-order geometric continuity, with no corner or cusp. Its nonzero tangent vector points vertically downward.

The second derivatives do not agree:So this is $C^1$ but not $C^2$ parametric continuity. The signed planar curvature $\kappa =(x^{\prime }{y}^{\prime \prime }-y^{\prime }{x}^{\prime \prime })/(x^{\prime 2}+y^{\prime 2}{)}^{3/2}$ has one-sided valuesThe unsigned curvatures agree, but the bending switches sides; there is no second-order geometric continuity through a regular orientation-preserving reparametrization. The join is a reversal of bending with a curvature jump, rather than a smooth zero-curvature inflection.

For the “gradient” compute $dy/dx=y^{\prime }/x^{\prime }$ away from the join:HenceThe zero horizontal derivative is not a stationary point of the parametric curve, since its vertical derivative is $-2$. It means that the locally regular curve has a vertical tangent line and cannot have a finite graph derivative as $y(x)$ there.

Assign one unit parameter interval to each piece. ThenThere is no ambiguity at $u=1$, since both pieces give the origin. For a single B-spline representation take degree two, the four de Boor pointsand the equally spaced spline knot vector $\tau =(-2,-1,0,1,2,3,4)$. With $N_{i,2}$ denoting the normalized degree-two B-spline on this vector, the complete valid parameter interval is $[{\tau }_2,{\tau }_4]=[0,2]$ andOn $[0,1]$ the active handles are $D_0,D_1,D_2$, and on $[1,2]$ they are $D_1,D_2,D_3$. Shared handles and a simple interior spline knot are what merge the two pieces into one uniform B-spline. The exterior spline knots support the basis; they do not extend the interval being drawn.

In particular, the requested horizontal pieces and their vertical counterparts are

Rotating the geometry through $180^{\circ }$ sends every point $p$ to $-p$. To start the extension at the origin, also reverse the parameter:Then $E(0)=(0,0)=F(1)$ and $E(1)=(2,0)$. Merely using $-F(t)$ would trace the same rotated image toward the origin, instead of away from the join.

The reversed and rotated de Boor points are $-D_2,-D_1,-D_0$, namely $(0,1),(0,-1),(4,1)$. The first two are already $D_1,D_2$, so there is only one new de Boor point, $\boxed{D_3=(4,1)}$. Using the same uniform basis matrix,Equivalently, the Bézier curve handles are $C=(0,0)$, $-B=(0,-1)$ and $-A=(2,0)$, which gives the same polynomials immediately.

Choose a quadratic uniform B-spline segment on a unit spline knot interval. This choice is useful because adjacent pieces can later share de Boor points at simple, equally spaced spline knots. Its three active basis pieces on local $t\in [0,1]$ areThey follow from the Cox-de Boor recurrence for degree two and consecutive integer spline knots. If the three de Boor points are $D_0,D_1,D_2$, then the equivalent Bézier curve handles areOne can verify this conversion simply by substituting these expressions into the Bernstein basis formula and collecting each $D_i$. Solving givesThe desired matrix representation is thereforeThe left row is again the monomial row, the middle matrix contains the monomial coefficients of $b_0,b_1,b_2$, and the right matrix lists the de Boor points. Unlike the Bézier curve basis matrix, the constant row averages two handles. A clamped B-spline with repeated end spline knots could instead reuse $A,B,C$ directly; the simple uniform convention above specifies which representation is being used and supplies the shared handles required for the extension.

Use a row of descending monomials $T(t)=[t^{2}t1]$ and a matrix with one control point per row. Expanding $(1-t{)}^2,2t(1-t),t^2$ gives their coefficients in the three columns of the basis matrix:The matrix multiplication isIn particular, $T(t)M_B=[(1-t{)}^{2}2t(1-t)t^2]$, so multiplying the geometric matrix takes exactly the weighted control point sum in part (a). The two output entries are $F_x(t),F_y(t)$. The basis matrix depends only on the degree and ordering convention; $G_B$ holds the particular geometry.

Three useful geometric properties, with their concrete consequences here, are:

These give the compact answerThe same sum-to-one calculation also explains affine equivariance of a geometric basis: applying an affine map to the handles applies that map to the curve.

For a fixed $t\in [0,1]$, De Casteljau's algorithm first takes the same fractional position along both adjacent sides of the control polygon:It then applies another linear interpolation with that same $t$:This is the degree-two Bernstein basis representation of a quadratic Bézier curve. Its coordinate polynomials areThe degree is exactly two, since its second derivative $(-4,-4)$ is nonzero. As a check on the construction, at $t=1/2$ the two intermediate points are $(-1,1/2)$ and $(0,1/2)$ and their midpoint is $F(1/2)=(-1/2,1/2)$.

Insert the union subtree from part (f) as another child of the original intersection:Thus the constructive solid geometry tree has one intersection root, four original half-space leaves and two union children. The first union handles the inward corner at $C$; the second embeds the circular fillet at $B$. The line segments $AB$ and $BC$ now end at $M$ and start at $N$, with the chosen circular arc between them. All other boundary line segments are retained.