October 7, 2003 Lecture 10: Convex Hulls in 3D 1 / 41Convex Hullsin 3-space(slides mostly by Jason C. Yang)October 7, 2003 Lecture 10: Convex Hulls in 3D 2 / 41Problem Statement• Given P: set of n points in 3D• Return:– Convex hull of P: CH(P), i.e.smallest polyhedron s.t. all elements of P on or inthe interior of CH(P).October 7, 2003 Lecture 10: Convex Hulls in 3D 3 / 41• Complexity of CH for n points in 3D is O(n)• ..because the number of edges of a convex polytope with n vertices is at most 3n-6 and the number of facets is at most 2n-4• ..because the graph defined by vertices and edges of a convex polytope is planar• Euler’s formula: n – ne+ nf= 2ComplexityOctober 7, 2003 Lecture 10: Convex Hulls in 3D 4 / 41Complexity• Each face has at least 3 arcs• Each arc incident to two faces2ne ≥ 3nf• Using Eulernf≤ 2n-4 ne≤ 3n-6October 7, 2003 Lecture 10: Convex Hulls in 3D 5 / 41Algorithm• Randomized incremental algorithm• Steps:– Initialize the algorithm– Loop over remaining pointsAdd prto the convex hull of Pr-1to transform CH(Pr-1) to CH(Pr)[for integer r≥1, let Pr:={p1,…,pr} ]October 7, 2003 Lecture 10: Convex Hulls in 3D 6 / 41Initialization• Need a CH to start with• Build a tetrahedron using 4 points in P– Start with two distinct points in P, say, p1and p2– Walk through P to find p3that does not lie on the line through p1and p2– Find p4that does not lie on the plane through p1, p2, p3– Special case: No such points exist? Planar case!• Compute random permutation p5,…,pnof the remaining pointsOctober 7, 2003 Lecture 10: Convex Hulls in 3D 7 / 41Inserting Points into CH• Add prto the convex hull of Pr-1to transform CH(Pr-1) to CH(Pr)• Two Cases:1) Pris inside or on the boundary of CH(Pr-1)– Simple: CH(Pr) = CH(Pr-1)2) Pris outside of CH(Pr-1) – the hard caseOctober 7, 2003 Lecture 10: Convex Hulls in 3D 8 / 41Case 2: Proutside CH(Pr-1)• Determine horizon of pron CH(Pr-1)– Closed curve of edges enclosing the visibleregion of pron CH(Pr-1)October 7, 2003 Lecture 10: Convex Hulls in 3D 9 / 41Visibility• Consider plane hfcontaining a facet f of CH(Pr-1)• fis visible from a point p if that point lies in the open half-space on the other side of hfOctober 7, 2003 Lecture 10: Convex Hulls in 3D 10 / 41Rethinking the Horizon– Boundary of polygon obtained from projecting CH(Pr-1) onto a plane with pras the center of projectionOctober 7, 2003 Lecture 10: Convex Hulls in 3D 11 / 41CH(Pr-1)  CH(Pr)• Remove visible facets from CH(Pr-1)• Found horizon: Closed curve of edges of CH(Pr-1)• Form CH(Pr) by connecting each horizon edge to prto create a new triangular facetOctober 7, 2003 Lecture 10: Convex Hulls in 3D 12 / 41Algorithm So Far…• Initialization– Form tetrahedron CH(P4) from 4 points in P– Compute random permutation of remaining pts.• For each remaining point in P– pris point to be inserted– If pris outside CH(Pr-1) then• Determine visible region• Find horizon and remove visible facets• Add new facets by connecting each horizon edge to prHow do we determine the visible region?October 7, 2003 Lecture 10: Convex Hulls in 3D 13 / 41How to Find Visible Region• Naïve approach:– Test every facet with respect to pr– O(n2) work• Trick is to work ahead:Maintain information to aid in determining visible facets.October 7, 2003 Lecture 10: Convex Hulls in 3D 14 / 41Conflict Lists• For each facet f maintainPconflict(f) ⊆{pr+1, …, pn}containing points to be inserted that can see f• For each pt, where t > r, maintain Fconflict(pt)containing facets of CH(Pr) visible from pt• p and f are in conflict because they cannot coexist on the same convex hullOctober 7, 2003 Lecture 10: Convex Hulls in 3D 15 / 41Conflict Graph G• Bipartite graph – pts not yet inserted– facets on CH(Pr)• Arc for every point-facet conflict• Conflict sets for a point or facet can be returned in linear timeAt any step of our algorithm, we know all conflicts between the remaining points and facets on the current CHOctober 7, 2003 Lecture 10: Convex Hulls in 3D 16 / 41Initializing G• Initialize G with CH(P4) in linear time• Walk through P5-nto determine which facet each point can seef1f2p6p5p7p6p7p5f2f1GOctober 7, 2003 Lecture 10: Convex Hulls in 3D 17 / 41Updating G• Discard visible facets from prby removing neighbors of prin G• Remove prfrom G• Determine new conflictsp6p7p5f2f1Gf1f2f3f3p6p7p5f2f1Gp6p7p5f2f1Gp5p7p6October 7, 2003 Lecture 10: Convex Hulls in 3D 18 / 41Determining New Conflicts• If ptcan see new f, it can see edge e of f.• e on horizon of pr, so e was already in and visible from ptin CH(Pr-1)• If ptsees e, it saw either f1or f2in CH(Pr-1)• Ptwas in Pconflict(f1) or Pconflict(f2) in CH(Pr-1)ptOctober 7, 2003 Lecture 10: Convex Hulls in 3D 19 / 41Determining New Conflicts• Conflict list of f can be found by testing the points in the conflict lists of f1and f2incident to the horizon edge e in CH(Pr-1)ptOctober 7, 2003 Lecture 10: Convex Hulls in 3D 20 / 41What About the Other Facets?• Pconflict(f) for any f unaffected by prremains unchangedpt• Pconflict(f) for any f unaffected by prremains unchanged• Deleted facets not on horizon already accounted forOctober 7, 2003 Lecture 10: Convex Hulls in 3D 21 / 41Final Algorithm• Initialize CH(P4) and G• For each remaining point– Determine visible facets for prby checking G– Remove Fconflict(pr) from CH– Find horizon and add new facets to CH and G– Update G for new facets by testing the points in existing conflict lists for facets in CH(Pr-1)incident to e on the new facets– Delete prand Fconflict(pr) from GOctober 7, 2003 Lecture 10: Convex Hulls in 3D 22 / 41Fine Point• Coplanar facets– prlies in the plane of a face of CH(Pr-1)• f is not visible from prso we merge created triangles coplanar to f• New facet has same conflict list as existing facetOctober 7, 2003 Lecture 10: Convex Hulls in 3D 23 / 41AnalysisOctober 7, 2003 Lecture 10: Convex Hulls in 3D 24 / 41Expected Number of Facets Created• Will show that expected number of facets created by our algorithm is at most 6n-20• Initialized with a tetrahedron = 4 facetsOctober 7, 2003 Lecture 10: Convex Hulls in 3D 25 / 41Expected Number of New Facets• Backward analysis:– Remove prfrom CH(Pr)– Number of facets removed same as those created by pr– Number of edges incident to prin CH(Pr) is degree ofpr:deg(pr, CH(Pr))October 7, 2003 Lecture 10: