(计算机图形学)lecture4Incremental Construction.ppt

Computational Geometry2D Convex Hulls (continued) Joseph S. B. Mitchell Stony Brook University O(n log n) : Incremental Construction Add points in the order given: v1 ,v2 ,…,vn Maintain current Qi = CH(v1 ,v2 ,…,vi ) Add vi+1 : If vi+1 ? Qi , do nothing Else insert vi+1 by finding tangencies, updating the hull Worst-case cost of insertion: O(log n) But, uses complex data structures * Point location test: O(log n) Binary search: O(log n) O(n log n) : Randomized Incremental Add points in random order Keep current Qi = CH(v1 ,v2 ,…,vi ) Add vi+1 : If vi+1 ? Qi , do nothing Else insert vi+1 by finding tangencies, updating the hull Expected cost of insertion: O(log n) * Each uninserted vj ? Qi (ji+1) points to the bucket (cone) containing it; each cone points to the list of uninserted vj ? Qi within it (with its conflict edge) * vi+1 e Add vi+1 ? Qi : Start from “conflict” edge e, and walk cw/ccw to establish new tangencies from vi+1 , charging walk to deleted vertices Rebucket points in affected cones (update lists for each bucket) Total work: O(n) + rebucketing work E(rebucket cost for vj at step i) = O(1) ? P(rebucket) ? O(1) ? (2/i ) = O(1/i ) E(total rebucket cost for vj ) = ? O(1/i ) = O(log n) Total expected work = O(n log n) Backwards Analysis: vj was just rebucketed iff the last point inserted was one of the 2 endpoints of the (current) conflict edge, e, for vj vj Output-Sensitive: O(n log h) The “ultimate” convex hull (in 2D) “Marriage before Conquest” : O(n log h) Lower bound ?(n log h) [Kirkpatrick Seidel’86] Simpler [Chan’95] 2 Ideas: Break point set S into groups of appropriate size m (ideally, m = h) Search for the “right” value of m ( =h, which we do not know in advance) by repeated squaring * h = output size So, O(n log h) is BEST POSSIBLE, as function of n and h !! Chan’s Algorithm Break S into n/m groups, each of size m Find CH of each group (using, e.g., Graham scan): O(m log m) per group