计算几何(研究生)全册配套课件3.ppt

计算几何计算几何 (( 研究生研究生 )) 全全册配套课件册配套课件 33Computational GeometryComputational Geometry2D Convex Hulls2D Convex HullsJoseph S. B. MitchellStony Brook UniversityComparing O(n), O(n log n), O(nComparing O(n), O(n log n), O(n22))33 n n log n n²210 10³ 10 • 210  104 220  106220  106 20 • 220  2 • 107 240 1012InteractiveProcessing n log n algorithms n² algorithmsn = 1000 yes ?n = 1000000 ? noFunction T(n) is O(f(n)) if there exists a constant C such that , for sufficiently large n, T(n) < C f(n)ConvexityConvexity Set Set XX is is c...