Convex Hulls in 3-spaceProblem StatementAlgorithmInitializationInserting Points into CHCase 2: Pr outside CH(Pr-1)VisibilityRethinking the HorizonCH(Pr-1)  CH(Pr)Algorithm So Far…How to Find Visible RegionConflict ListsConflict Graph GInitializing GUpdating GDetermining New ConflictsSlide 17What About the Other Facets?Final AlgorithmFine PointAnalysisComplexitySlide 23Expected Number of Facets CreatedExpected Number of New FacetsExpected Degree of prExpected Number of Created FacetsRunning TimeTotal Time to Find New ConflictsRandomized Insertion OrderSlide 31Convex Hulls in Dual SpaceHalf-Plane IntersectionSlide 34Voronoi Diagrams RevisitedVoronoi DiagramsSimplified CaseDemoDelaunay Triangulations from CHHigher Dimensional Convex HullsSlide 411 / 41Convex Hullsin 3-spaceJason C. Yang2 / 41Problem Statement•Given P: set of n points in 3-space•Return:–Convex hull of P: CH(P)–Smallest polyhedron s.t. all elements of P on or inthe interior of CH(P).3 / 41Algorithm•Randomized incremental algorithm•Steps:–Initialize the algorithm–Loop over remaining pointsAdd pr to the convex hull of Pr-1 to transform CH(Pr-1) to CH(Pr)[for integer r1, let Pr:={p1,…,pr}]Main Idea:Incrementally insert new points into the running/intermediate Convex Hull.4 / 41Initialization•Need a CH to start with•Build a tetrahedron using 4 points in P–Start with two distinct points in P: p1 and p2–Walk through P to find p3 that does not lie on the line through p1 and p2–Find p4 that does not lie on the plane through p1, p2, p3–Special case: No such points exist?•Compute random permutation p5,…,pn of the remaining points•Need a CH to start with•Build a tetrahedron using 4 points in P–Start with two distinct points in P: p1 and p2–Walk through P to find p3 that does not lie on the line through p1 and p2–Find p4 that does not lie on the plane through p1, p2, p3–Special case: No such points exist?All points lie on a plane. Use planar CH algorithm!•Compute random permutation p5,…,pn of the remaining points5 / 41Inserting Points into CH•Add pr to the convex hull of Pr-1 to transform CH(Pr-1) to CH(Pr)[for integer r1, let Pr:={p1,…,pr}]•Two Cases:1) Pr is inside or on the boundary of CH(Pr-1)Trivial: CH(Pr) = CH(Pr-1)2) Pr is outside of CH(Pr-1)6 / 41Case 2: Pr outside CH(Pr-1)•Determine horizon of pr on CH(Pr-1)–Closed curve of edges enclosing the visible region of pr on CH(Pr-1)7 / 41Visibility•Consider plane hf containing a facet f of CH(Pr-1)•f is visible from a point if that point lies in the open half-space on the other side of hf8 / 41Rethinking the Horizon–Boundary of polygon obtained from projecting CH(Pr-1) onto a plane with pr as the center of projection9 / 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 pr to create a new triangular facet10 / 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–pr is point to be inserted–If pr is 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?11 / 41How to Find Visible Region•Naïve approach:–Test every facet with respect to pr–O(n2)•Trick is to work ahead:Maintain information to aid in determining visible facets.12 / 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, maintainFconflict(pt) containing facets of CH(Pr) visible from pt•p and f are in conflict because they cannot coexist on the same convex hull13 / 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 CH14 / 41Initializing G •Initialize G with CH(P4) in linear time•Walk through P5-n to determine which facet each point can seef1f2p6p5p7p6p7p5f2f1G15 / 41Updating G•Discard visible facets from pr by removing neighbors of pr in G•Remove pr from G•Determine new conflictsp6p7p5f2f1Gf1f2f3f3p6p7p5f2f1Gp6p7p5f2f1Gp5p7p616 / 41Determining New Conflicts•If pt can see new f, it can see edge e of f.•e on horizon of pr, so e was already in and visible from pt in CH(Pr-1)•If pt sees e, it saw either f1 or f2 in CH(Pr-1)•Pt was in Pconflict(f1) or Pconflict(f2) in CH(Pr-1)pt17 / 41Determining New Conflicts•Conflict list of f can be found by testing the points in the conflict lists of f1 and f2 incident to the horizon edge e in CH(Pr-1)pt18 / 41What About the Other Facets?•Pconflict(f) for any f unaffected by pr remains unchangedpt•Pconflict(f) for any f unaffected by pr remains unchanged•Deleted facets not on horizon already accounted for19 / 41Final Algorithm•Initialize CH(P4) and G•For each remaining point–Determine visible facets for pr by 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 pr and Fconflict(pr) from G20 / 41Fine Point•Coplanar facets–pr lies in the plane of a face of CH(Pr-1)•f is not visible from pr so we merge created triangles coplanar to f•New facet has same conflict list as existing facet21 / 41Analysis22 / 41•Complexity of CH for n points in 3-space is O(n)•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•From Euler’s formula: n – ne + nf = 2Complexity23 / 41Complexity•Each face has at least 3 arcs•Each arc incident to two faces2ne  3nf•Using Eulernf  2n-4 ne  3n-624 / 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 facets25 / 41Expected Number of New Facets•Backward analysis:–Remove pr from CH(Pr)–Number of facets removed same as those created by pr–Number of edges incident to pr in CH(Pr) is degree of pr:deg(pr, CH(Pr))26 / 41Expected Degree of pr•Convex polytope of r vertices has at most 3r-6 edges•Sum of degrees