Convex hulls 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 more definitions are needed Convex hulls 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 facets sharing a point A simple polyhedron partitions 3 space into two domains the interior bounded and the exterior unbounded The term polyhedron often means boundary interior A simple polyhedron is convex if its interior is a convex set A polyhedron is the 3 dimensional equivalent of a polygon Convex hulls 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 The terms convex d polytope d polytope and polytope are all equivalent Theorem The convex hull of a finite set of points in Ed is a convex d polytope Conversely a polytope is the convex hull of a finite set of points For d 3 the convex hull is a convex polyhedron For arbitrary d the convex hull is a d polytope Convex hulls 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 In general an affine set for given k is a flat object of k 1 dimensions Given a subset L of Ed the affine hull aff L is the smallest affine set containing L If L is 2 points or a segment aff L is a line If L is 3 points or a planar polygon aff L is a plane A set of k points is affinely independent if no subset of them can generate the same affine set The text sometimes refers to affine sets as hyperplanes Convex hulls 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 d d 1 d 2 1 0 Face d face d 1 face d 2 face 1 face 0 face Name of face d polytope facet subfacet edge vertex For a 3 polytope polyhedron Dimension d 3 d 1 2 d 2 1 0 Face 3 face 2 face 1 face 0 face Name of face 3 polytope polyhedron facet planar polygon subfacet edge vertex Convex hulls 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 0 1 2 3 d simplex vertex edge triangle tetrahedron 2 simplex convex hull of 2 1 points not a 2 simplex convex hull of 2 1 points Convex hulls 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 2 simplex convex hull of 2 1 points not a 2 simplex convex hull of 2 1 points not a 2 simplex convex hull of 2 1 points Convex hulls 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 p1 is beyond F aff F F P p2 is beneath F Note error in text 2nd paragraph of 3 4 the P should be p Convex hulls Gift wrapping d 2 Gift wrapping Proposed by Chand and Kapur 1970 Analyzed by Bhattacharya 1982 Specialized for d 2 by Jarvis 1973 Jarvis march Key idea Given one facet a d 1 face of the convex hull find a neighboring facet of the hull by wrapping a d 1 dimensional affine set around the point set Continue from each facet to its neighbors until all facets are found For example in d 3 imagine wrapping a sheet of 2 dimensional wrapping paper around a 3 dimensional gift box In d 2 Jarvis march a 1 dimensional line is wrapped around a 2 dimensional point set My presentation will often appeal to d 3 for expository purposes but the method is applicable for any d 2 Convex hulls Gift wrapping d 2 Simplicial assumption As presented here and in the text the algorithm assumes that the resulting polytope the convex hull is simplicial Recall that in a simplicial d polytope each facet is a d 1 simplex and is determined by exactly d vertices There will be no points in S coplanar with the d vertices that determine each facet of the convex hull Theorem In a simplicial d polytope a subfacet is shared by exactly two facets and two facets F1 and F2 share a subfacet e iff e is …