(计算机图形学)lecture2Computational Geometry 2D Convex Hulls.ppt

Computational Geometry2D Convex Hulls Joseph S. B. Mitchell Stony Brook University Comparing O(n), O(n log n), O(n2) * n n log n n2 210 ?103 10 ? 210 ? 104 220 ? 106 220 ? 106 20 ? 220 ? 2 ? 107 240 ?1012 Interactive Processing n log n algorithms n2 algorithms n = 1000 yes ? n = 1000000 ? no Function T(n) is O(f(n)) if there exists a constant C such that , for sufficiently large n, T(n) C f(n) Convexity Set X is convex if p,q?X ? pq? X Point p? X is an extreme point if there exists a line (hyperplane) through p such that all other points of X lie strictly to one side Fact: If X=S is a finite set of points in 2D, then CH(X) is a convex polygon whose vertices (extreme points) are points of S. * p q r Extreme points in red p q non-convex q p convex Equivalent Definitions of Convex Hull, CH(X) Set-theoretic “smallest” convex set containing X. {all convex combinations of d+1 points of X } [Caratheodory’s Thm] (in any dimension d) In 2D: min-area (or min-perimeter) enclosing convex body containing X In 2D: * Convexity Fact: If X=S is a finite set of points in 2D, then CH(X) is a convex polygon whose vertices (extreme points) are points of S. * p4 p1 p3 p6 p5 p8 p7 p9 Input: n points S = (p1, p2, …, pn) Output: A boundary representation, e.g., ordered list of vertices (extreme points), of the convex hull, CH(S), of S (convex polygon) Fundamental Problem: 2D Convex Hulls * More generally: CH(polygons) p4 p1 p3 p2 p6 p5 p8 p7 p9 Output: (9,6,4,2,7,8,5) 2D Convex Hull Algorithms O(n4) simple, brute force (but finite!) O(n3) still simple, brute force O(nh) simple, “output-sensitive” h = output size (# vertices) O(n log n) worst-case optimal (as fcn of n) O(n log h) “ultimate” time bound (as fcn of n,h) Randomized, expected O(n log n) Lower bound: ?(n log n) * From SORTING: y= x2 xi (xi ,xi2 ) Simple, elegant Note: Even if the