Skip to content

Gift wrapping in higher dimensions: background and setup

Scope

  • Slides: pp. 264-271
  • Major topic folder: convex-hulls
  • Recording files touching this material: CS 564 - 03.04 12.1.txt, CS 564 - 03.06 13.1.txt
  • Goal of this file: You should be able to study this topic without reopening the slide deck.

Big picture

The moment d becomes bigger than 2, hull representation changes completely. You no longer output a cyclic list of vertices; you output a polytope boundary made of facets.

What you must know cold

  • Point set in E^d, affine sets, faces, facets, simplices, simplicial polytopes.
  • Representation of the hull in higher dimensions by facets/subfacets.
  • Beneath relation for facets.

Core ideas and reasoning

  • In 2D the hull is a cycle; in higher dimensions the boundary is a complex of facets.
  • Gift wrapping in higher dimensions grows the hull facet by facet.

Figures to actually look at

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

Figure from slide p. 269

Figure from slide p. 269

Figure from slide p. 270

Figure from slide p. 270

Slide-by-slide digestion

p. 264 - Gift wrapping, d > 2

  • Problem definition
  • CONVEX HULL, D > 2
  • INSTANCE. Set S = { p1, p2, … pN} of points in d-space (Ed).
  • QUESTION. Construct the convex hull H(S) of S.
  • The coordinates of the points pi ∈S will be referred to as
  • pi = (x1, x2, …, xd).
  • For d = 2, the constructed hull was given (represented)
  • as a sequence of hull vertices.
  • How is the hull represented for d > 2?
  • To answer that, and describe the algorithm,

p. 265 - Gift wrapping, d > 2

  • Polyhedron
  • In E3 a polyhedron is defined by a finite set of planar polygons
  • such that every edge of a polygon is shared by exactly one
  • other polygon and no subset of the polygons has the property.
  • Polyhedra is plural for polyhedron.
  • The polygons that share an edge are adjacent.
  • The vertices and edges of the polygons
  • are the vertices and edges of the polyhedron.
  • The polygons are the facets of the polyhedron.
  • A polyhedron is simple if there is no pair of nonadjacent

p. 266 - Gift wrapping, d > 2

  • Polytope
  • A half-space is the portion of Ed lying on one side of a hyperplane.
  • A polyhedral set in Ed is the intersection of a finite set of
  • closed half-spaces.
  • Note that a polyhedral set is convex, since a half-space is convex,
  • and the intersection of convex sets is convex.
  • Plane polygons (d = 2) and space polyhedra (d = 3) are
  • 2- and 3-dimensional instances of bounded polyhedral sets.
  • A bounded d-dimensional polyhedral set is a polytope.
  • Note that polytopes are convex by definition.

p. 267 - Gift wrapping, d > 2

  • Affine set
  • Given k distinct points p1, p2, …, pk in Ed, the set of points
  • p = α1p1 + α2p2 + . . . + αkpk
  • (αj ∈ℜ, α1 + α2 + . . . + αk = 1)
  • is the affine set generated by p1, p2, …, pk,
  • and p is an affine combination of p1, p2, …, pk.
  • We have seen this before.
  • If k = 2, this is the parametric equation of a line,
  • i.e., a line is an affine set.
  • For k = 3, the affine set is a plane.

p. 268 - Gift wrapping, d > 2

  • Faces of a polytope
  • A d-polytope is described by its boundary,
  • which consists of faces. For a d-polytope,
  • there are faces in all dimensions 1 … d.
  • Some have special names.
  • For a d-polytope:
  • Dimension
  • Face
  • Name of face
  • d-face

p. 269 - Gift wrapping, d > 2

  • Simplex
  • A d-polytope P is a d-simplex (or just simplex)
  • iff it is the convex hull of (d + 1) affinely independent points.
  • Any subset of the d vertices of the convex hull is itself a
  • simplex and is a face (in some dimension) of P.
  • d-simplex
  • vertex
  • edge
  • triangle
  • tetrahedron

p. 270 - Gift wrapping, d > 2

  • Simplicial
  • A d-polytope is simplicial if each of its facets is a (d-1)-simplex.
  • For example, for d = 3:
  • The convex hull of a set of points in 3-space (the convex hull
  • is a 3-polytope) is simplicial iff every facet is a 2-simplex
  • (a triangular convex hull of exactly 3 points).
  • For example, the first case below.
  • If any facet of the hull has > 3 co-planar points,
  • the hull is not simplicial.
  • For example, the second and third cases below.

p. 271 - Gift wrapping, d > 2

  • Beneath
  • A point p is beneath a facet F of a polytope P if the point p
  • lies in the open half-space determined by hyperplane aff(F)
  • and containing P.
  • In other words, aff(F) is a supporting hyperplane of P,
  • and p and P are in the same half-space bounded by aff(F).
  • Point p is beyond facet F if p lies in the open half-space
  • determined by aff(F) and not containing P.
  • The figure shows these relationships for d = 2.
  • Note error in text, 2nd paragraph of 3.4, “the P” should be “p”.

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

  • Give the precise definitions.
  • Distinguish similar notions cleanly.
  • Use the right primitive test or formula on a concrete example.

Complexity and performance facts

Representation complexity now depends on the number of facets and on dimension d.

Common mistakes and danger points

  • Do not describe the d>2 hull as an ordered list of vertices. That loses the boundary structure.

Exam-style drills and answer skeletons

Definition drill

Question. Give the precise definitions and the most important consequences from gift wrapping in higher dimensions: background and setup.

How to answer. A strong answer distinguishes similar objects and uses the course terminology exactly.

Recap

What you must know cold

  • Point set in E^d, affine sets, faces, facets, simplices, simplicial polytopes.
  • Representation of the hull in higher dimensions by facets/subfacets.
  • Beneath relation for facets.

Core test / key idea

  • In 2D the hull is a cycle; in higher dimensions the boundary is a complex of facets.
  • Gift wrapping in higher dimensions grows the hull facet by facet.

Complexity

  • Representation complexity now depends on the number of facets and on dimension d.

Common mistakes / danger points

  • Do not describe the d>2 hull as an ordered list of vertices. That loses the boundary structure.

End-of-file summary

  • Point set in E^d, affine sets, faces, facets, simplices, simplicial polytopes.
  • Representation of the hull in higher dimensions by facets/subfacets.
  • Beneath relation for facets.
  • Representation complexity now depends on the number of facets and on dimension d.
  • Do not describe the d>2 hull as an ordered list of vertices. That loses the boundary structure.