Skip to content

Gift wrapping in higher dimensions: supporting hyperplanes, initialization, candidates, and analysis

Scope

  • Slides: pp. 280-289
  • Major topic folder: convex-hulls
  • Recording files touching this material: CS 564 - 03.06 13.2.txt
  • Goal of this file: You should be able to study this topic without reopening the slide deck.

Big picture

This range covers the hard parts in d>2: getting the first facet, generating candidate subfacets, and accounting for the cost in terms of facets and dimension.

What you must know cold

  • Supporting hyperplanes as the higher-dimensional version of supporting lines.
  • Initialization by successively finding supporting hyperplanes.
  • Candidate subfacets and frontier maintenance.
  • Final cost accounting.

Core ideas and reasoning

  • Initialization is not trivial: you need one valid hull facet before adjacency expansion can begin.
  • Each processed facet generates subfacet candidates; some are already internal, others remain frontier pieces.

Figures to actually look at

These are cropped from the main slide PDF. Do not skip them.

Figure from slide p. 283

Figure from slide p. 283

Figure from slide p. 284

Figure from slide p. 284

Slide-by-slide digestion

p. 280 - Gift wrapping, d > 2

  • Supporting lines and planes
  • Recall that a supporting line of a convex polygon intersects the
  • polygon at a vertex such that the entire polygon is to one side of
  • the line.
  • A supporting plane (or hyperplane) has a similar relationship
  • with a polytope.
  • polygon, d = 2
  • supporting line, d = 1
  • intersection is vertex
  • intersection is edge

p. 281 - Gift wrapping, d > 2

  • Step 2. “Find an initial convex hull facet.”, 1
  • The idea is to obtain a hyperplane containing a facet of the
  • convex hull polytope H(S) by successive approximations.
  • This is done by constructing a sequence of d (d is dimension Ed)
  • supporting hyperplanes π1, π2, …, πd,
  • such that πi shares one more vertex with the convex hull than πi-1
  • for 1 ≤i ≤d (we define π0 as sharing 0 vertices with H(S)).
  • In other words, πi for 1 ≤i ≤d shares i vertices with H(S).
  • A supporting hyperplane intersects the polytope
  • such that the entire polytope is to one side of the hyperplane.

p. 282 - Gift wrapping, d > 2

  • Step 2. “Find an initial convex hull facet.”, 2
  • For d = 3 (E3) the successive hyperplanes intersect
  • the convex hull as follows:
  • supporting

  • vertices

  • intersection
  • hyperplane
  • of H(S) on πi
  • object
  • π0

p. 283 - Gift wrapping, d > 2

  • Step 2. “Find an initial convex hull facet.”, 3
  • Thus we begin by determining a point of least x1-coordinate
  • (call it p1′); p1′ is certainly a vertex (a 0-face) of the convex hull.
  • Hyperplane π1 is chosen orthogonal to vector (1, 0, …, 0)
  • and passing by (containing) p1′.
  • In other words, π1 passes through p1′
  • and is parallel to the x2x3…xd hyperplane.
  • For example, for d = 3:
  • This “initializes” the process of finding
  • the initial supporting hyperplane.

p. 284 - Gift wrapping, d > 2

  • Step 2. “Find an initial convex hull facet.”, 4
  • At the jth iteration, 2 ≤j ≤d, the hyperplane πj-1 has
  • normal vector nj-1 and contains vertices p1′, p2′, …, pj-1′.
  • We need to find pj′ to define πj.
  • Through vector calculations pj′ can be found
  • such that πj (defined by p1′, p2′, …, pj′) has the largest angle
  • with πj-1 (defined by p1′, p2′, …, pj-1′).
  • Each iteration requires O(Nd) + O(d2) time.
  • There are d iterations, so finding the initial supporting
  • hyperplane πd required by step 2 of the overall algorithm

p. 285 - Gift wrapping, d > 2

  • Step 7. “Generate the subfacets of facet F.”
  • Because we have assumed that the convex hull polytope H(S)
  • is simplicial, each facet of H(S) is determined by exactly d vertices,
  • and each subset of those vertices of size d-1 determines a subfacet.
  • The subfacets of a facet can be generated in a straightforward
  • fashion by considering each of the d vertices in turn and reading
  • off the remaining d-1 vertices.
  • This requires O(d2) time.
  • Each facet will be described by a d-component vector
  • of the indices of its vertices,

p. 286 - Gift wrapping, d > 2

  • Step 8. “Check if a subfacet e is a candidate.”, 1
  • A subfacet is a candidate iff it is contained in just one facet
  • generated by the algorithm.
  • Why just one?
  • Recall that in a simplicial polytope, a subfacet is shared by exactly
  • two facets. If a subfacet is generated twice,
  • then both of its adjacent facets have been found,
  • and the subfacet is of no further use.

p. 287 - Gift wrapping, d > 2

  • Step 8. “Check if a subfacet e is a candidate.”, 2
  • Recall that ℑis a file of subfacets.
  • Given a newly generated subfacet e,
  • searching ℑfor e will determine if e is a candidate.
  • If e ∈ℑ, delete e.
  • If e ∉ℑ, add it. (This is step 10 in the algorithm).
  • A subfacet is represented by a (d-1)-component vector
  • of vertex indices.
  • Store ℑas a height-balanced binary tree,
  • ordered lexicographically on the vertex indices.

p. 288 - Gift wrapping, d > 2

  • Analysis, 1
  • We analyze the algorithm in steps.
  • Let ϕd-1 be the actual number of facets of the polytope H(S).
  • Let ϕd-2 be the actual number of subfacets of the polytope H(S).
  • Initialization (steps 1-4) requires O(Nd2) time.
  • Steps 6, 11, 12 process each facet once each,
  • adding it to the queue, removing it, and outputting it;
  • they require O(d) × ϕd-1.
  • number of facets
  • components of the vector representing the facet

p. 289 - Gift wrapping, d > 2

  • Analysis, 2
  • It can be shown that both ϕd-1, ϕd-2 ∈O(N⎣d/2⎦).
  • Using this the previous analysis simplifies to:
  • Convex hull construction time in d dimensions on N points
  • T(d,N) using the Gift wrapping algorithm,
  • requires O(N⎣d/2⎦+1) + O(N⎣d/2⎦log N).
  • Note that even though d is a constant,
  • it remains in the final order expression where it is an exponent
  • of the input size N.

What you must be able to say or do in an exam

  • State the claim precisely before giving the argument.
  • Identify the known lower bound / recurrence / invariant you are using.
  • Keep the direction of the argument correct.
  • End with the exact asymptotic conclusion.

Complexity and performance facts

State the course bound in terms of N, dimension d, number of facets, and number of subfacets.

Common mistakes and danger points

  • Do not quote a simple O(N log N) style bound from 2D. The higher-dimensional complexity depends heavily on output size.

Exam-style drills and answer skeletons

Proof drill

Question. Explain the main argument in gift wrapping in higher dimensions: supporting hyperplanes, initialization, candidates, and analysis in a logically correct order.

How to answer. Do not jump from intuition to conclusion. State the reduction/invariant/recurrence first, then derive the claimed bound.

Recap

What you must know cold

  • Supporting hyperplanes as the higher-dimensional version of supporting lines.
  • Initialization by successively finding supporting hyperplanes.
  • Candidate subfacets and frontier maintenance.
  • Final cost accounting.

Core test / key idea

  • Initialization is not trivial: you need one valid hull facet before adjacency expansion can begin.
  • Each processed facet generates subfacet candidates; some are already internal, others remain frontier pieces.

Complexity

  • State the course bound in terms of N, dimension d, number of facets, and number of subfacets.

Common mistakes / danger points

  • Do not quote a simple O(N log N) style bound from 2D. The higher-dimensional complexity depends heavily on output size.

End-of-file summary

  • Supporting hyperplanes as the higher-dimensional version of supporting lines.
  • Initialization by successively finding supporting hyperplanes.
  • Candidate subfacets and frontier maintenance.
  • State the course bound in terms of N, dimension d, number of facets, and number of subfacets.
  • Do not quote a simple O(N log N) style bound from 2D. The higher-dimensional complexity depends heavily on output size.