Report

Convex Hulls Shmuel Wimer Bar Ilan Univ., Eng. Faculty Technion, EE Faculty May 2012 1 Preliminaries d E : d -dim insional E uclidean space. G iven k distinct points p1 , p 2 , points p 1 p1 2 p 2 + 1 i k , and by p1 , p 2 , p1 , p 2 , k i 1 d , p k in E , the set of + k p k , i R , i 0, i 1, is the con vex set generated , p k , and p is the con vex com bin ation of ,p k . d G iven L an arbitrary set of points in E , the con vex h u ll conv L is the sm allest convex set containing L . May 2012 2 A polyh edral set in E d is the intersection of finite set d of closed half-spaces (one side of a hyp erplane) in E . d C onvex d - polytop is a bounded polyhedral set in E . T h eorem : T he convex hull of a finite set of poin ts in E d is a convex polytop. C onversely, a conv ex polytop is the convex hull of a finite set of po ints. 2-polytop is a convex polygon, specified by the ordered set of its vertices. May 2012 3 3-polytop is a polyhedron com pletely spe cified by its vertices, edges and faces. Its projection on the plane or sphere is a planar graph. It follow s from E uler's form ula that the num ber of vertices e dges and faces of a 3D polyhedron are linearly related. H ow difficult is to find the convex hull of N points in the plane? T h eorem : S orting can be transform ed in linear-ti m e to finding convex hull in the plane. Fin dingthe convex hull of N points requires therefore N log N May 2012 t im e. 4 P roof : G iven N real positive num bers x1 , x 2 , consider the N points ,x N , x i , x i R 1 i N . T his 2 2 transform ation takes linear tim e, T he N points are the vertices y a convex polygon in the of y x plane. 2 Finding the polygon results in the sorting of x1 , x 2 , , x N , and the low er bound N log N May 2012 follow s. x 5 Convex Hull Algorithms in the Plane A point p of a convex set S is extrem e if no tw o points a , b S exist such that p a , b . T he set E of extrem e points in S is the sm allest subset of S such that conv E = conv S and E is the set of conv S vertices. Finding conv S of finite set of points S ca n be done by: 1. identifying its extrem e points, and 2. order those so that they form a conve x polygon. May 2012 6 T h eorem : A point p fails to be an extrem e point of a p1 plane convex set S only if p3 p0 it lies in som e triangle w ith vertices in S but is not itself p2 a vertex of the triangle. C orollary : L et S N . T he extrem e points of conv S can be found in O N 4 tim e. T he nature of the order of extrem e point s is revealed by the follow ing properties. May 2012 7 A ray em anating from an interior point o f a convex bounded figure F is intersecting the boun dary of F in exactly one point. C onsecutive vertices of a convex polygon occur in sorted angular order about any interior point. p2 p3 p4 q can be found in P p1 q p7 p5 p6 May 2012 O 1 tim e. vertices are sorted in O N log N tim e. 8 Graham’s Scan To determine whether a point is extreme, is it necessary to examine all triangles? R. L. Graham showed in 1972 that sorting the point first, the extreme points can be found in linear time. Suppose an internal point was found and was set as the origin, while all points are trivially transformed accordingly. The points can be sorted lexicographically by angle and distance from origin. The points are then stored in doublylinked circular list. No divisions or square roots are needed. May 2012 9 Scan starts at the lowest p3 p1 p2 rightmost point which is certainly extreme. p0 O Scan It repeatedly examines triples of consecutive points Start to determine whether or not they define a reflex angle. The following rules apply: 1. p1p2p3 is a right turn. Eliminate p2 and check p0p1p3. 2. p1p2p3 is a left turn. Advance the scan and check p2p3p4. May 2012 10 Theorem: The convex hull of N points in the plane can be found in O(NlogN) time and O(N) storage, using only arithmetic operations and comparisons. The sort of polar coordinate (divisions and square toot are not necessary) can be replaced by left to right sorting as follows. Upper subset Split into upper and Scan lower points by the r the leftmost and l Lower subset May 2012 line passing through rightmost points 11 Construct the upper and lower boundaries separately by left to right scan of the sorted points, and applying same rules for reflex angles. The points l and r are necessarily on the boundary. May 2012 12 Jarvis’s March A polygon can be described by the sequence of its edges, similar as the sequence of vertices. Given two points, it is straightforward to test whether the line segment joining them is an edge of the convex hull. Convex hull p Theorem: The line segment q l defined by two points is p an edge of a convex hull iff all other points of the set q lie on l or to one side of it. May 2012 13 There are O(N2) edges to examine. For each, all N points are tested, yielding O(N3) run time. O nce a segm ent p q is found to be a hull ed ge, there m ust be a succesive edge qr , and O N tests suffice . The algorithm finds p4 p3 successive hull vertices by repeatedly turning p2 angles. New vertex is discovered in O(N) time, p1 May 2012 yielding O(N2) total time. 14 In the worst case where all N points lie on the convex hull Jarvis’s march consumes O(N2) time, which is inferior to O(NlogN) Graham’s scan run time. In many cases where the number of convex hull points is h and h<<N, run time is O(hN). Jarvis’s march is reminiscent of gift-wrapping, and can be extended to 3D, while Graham’s scan does not. May 2012 15 QUICKHULL Techniques Inspired by QUICKSORT sorting algorithm (Hoare 1962). Reminder: QUICKSORT worst case run time is O(N2). Expected runs time is O(NlogN) (division of set into two subsets, adhering some “balance” criterion). QUICKHULL works recursively. It partitions the set S of N points into two subsets each results in a polygonal chain. The chains concatenations yields the convex hull polygon. The initial partitioning is defined by the line passing through the points with the smallest and largest abscissae. May 2012 16 L1 S S (1,1) h (1) S (1, 2 ) r L2 l May 2012 17 Find h S (1) hlr such that the triangle is m axim al am ong all triangles w hose area plr p S (1) . If there are few m axim al triangles, pick th e one w ith largest angle plr . T he point h is guaranteed to belong to the convex hull. T he points outside triangle sets. S (1,1) hlr split into sdisjoint are those left to L1 and S to L 2 . T he chains obtained from S (1, 2 ) (1,1) are those left and S (1, 2 ) are concatenated to form the upper chain w ith respect to lr . May 2012 18 point chain Q U IC K H U L L ( point set S ; point l , r ) { if ( S l , r ) return l, r ; // convex hull is an ed ge else { // get apex of m ax area tr ian g l e h F U R T H E S T ( S , l , r ); S (1) points of S l eft t o lh ; S points of S left to hr ; // chain concatenation (2) return Q U IC K H U L L ( S (1) , l , h )+ Q U IC K H U L L ( S (2) , h , r ); } } May 2012 19 Finding the point which maximizes the area of the triangle takes O(N). Chain concatenation takes O(1). Therefore, if the size of point subsets adheres some balance, the run time is O(NlogN). As QUICKSORT, worst run time is O(N2). Though QUICKHULL is a divide-and-conquer algorithm, the uncontrolled size of the two remaining parts results square worst-case time complexity. Moreover, the algorithm that inherently can be parallelized, may suffer from inefficiency due to poor balancing. May 2012 20 Divide-and-Conquer Algorithms Suppose the point set S is divided into two arbitrary halves S1 and S2, where there is no separation between S1 and S2. Let us compute the convex hulls CH(S1) and CH(S2). How much work is required to form CH(S1US2)? It follow s from C H S 1 S 2 C H C H S1 CH S2 that w e can w ork recursively. T he key qu estion is how efficiently can tw o convex hulls be m erg ed? May 2012 21 If U N is the tim e required for m erging and T N is the total run tim e, then T N 2 T N 2 U N . C H C H S1 CH S2 T o obtain T N O N log N , there m ust exist U N O N . Theorem: The convex hull of the union of two convex polygons can be found in time proportional to their total number of vertices. May 2012 22 P roof : P1 and P2 are convex polygons. 1. Find a point p internal to P1 (centroid of three vertices). It follow s that p C H P1 P2 . 2. D eterm ine w hether p P2 (can be done in O N t im e). In that case the vertices of both P1 a nd P2 occur in angular sorted order about p . P1 and P2 can be m erged in O N tim e by traversi ng their vertices in opposite angular order about p . May 2012 23 3. p P2 . A w edge vpu is thus defined and u and v can be found. T he inner chain of P2 from u to v can be discarded. A ll this takes T he points of the outer chain of P2 are so rted by angular order about p , and sam e for P1 . T he tw o lis ts are m erged ON tim e. G raham 's scan can now find C H P1 ON tim e. 4. G raham 's scan can find C H P1 May 2012 P2 in O N P2 in tim e. 24