算法合集之半平面交的新算法及其實(shí)用價(jià)值-wenkub
2022-10-31 20:30:45 本頁面
【正文】 21 Zeyuan Zhu 22 3. DivideandConquer Algorithm Divide: Partition the n hplanes into two sets of size n/2. Conquer: Compute feasible region recursively of both two subsets. Combine: Compute intersection of two convex region, by CPI167。π. 188。π]∪ (189。π]∪ (189。對極角相同的半平面，根據(jù)常數(shù)項(xiàng)保留其中之一。 ? Step 3: Starting from two hplanes with the least polar angle, pute their intersection. Push them two into a stack. November 12, 2021 Zeyuan Zhu 29 4. SortandIncremental Algorithm ?每次按照極角從小到大順序增加一個(gè)半平面，算出它與棧頂半平面的交點(diǎn)。我們有兩個(gè)點(diǎn)集， (189。π, π]給出下半個(gè) ? Step 4: Intersections of adjacent hplane pairs in stack form half a convex polygon. For the two sets, we have two halves – (189。π, π] gives a lower hull. November 12, 2021 Zeyuan Zhu 34 4. SortandIncremental Algorithm ?相鄰半平面的交點(diǎn)組成半個(gè)凸多邊形。π]∪ (189。π]∪ (189。通常我們用快速排序?qū)崿F(xiàn) Step2，總的時(shí)間復(fù)雜度為O(nlogn)，隱蔽其中的 常數(shù)因子 很小 November 12, 2021 Zeyuan Zhu 41 5. Conclusion and Practical Use 總結(jié)和實(shí)際應(yīng)用 November 12, 2021 Zeyuan Zhu 42 5. Conclusion and Practical Use Great ideas need landing gear as well as wings. Samp。I算法似乎和 Damp。C one. The program in C++ programming language takes less than 3KB. 新的 Samp。I a lgor ithm’ s c omplex ity is extraordinarily smaller than Damp。I算法復(fù)雜度中的系數(shù) ， 遠(yuǎn)小于Damp。 November 12, 2021 Zeyuan Zhu 45 5. Conclusion and Practical Use If the given hplanes are all in (189。C program may not. An informatics problem a p p e a r e d in U S A I n v i t a t i o n a l Computing Olympiad contest with such purpose. 如果給定半平面均在 (189。 USAICO比賽中就出現(xiàn)了這樣一題 。 山， 倒海翻江卷巨瀾。 。 山， 刺破青天鍔未殘。 Anyway O(n) approach usually runs s lowe r th an n logn on es fo r its additional memory usage! November 12, 2021 Zeyuan Zhu 47 5. Conclusion and Practical Use 美麗心靈 諾貝爾獎(jiǎng)得主 John Nash 原創(chuàng)的理論 ——original idea 創(chuàng)新與信息學(xué)競賽 創(chuàng)新與技術(shù) 我心目中的創(chuàng)新 ——最重要的是 思想創(chuàng)新 ， 其次是 行為 創(chuàng)新 ， 再其次是文章創(chuàng)新 ， 再再其次才是語言創(chuàng)新 思想 實(shí)踐 The principal mark of genius is not perfection but originality, the opening of new frontiers. Authur Koestler (1905 1983) Hungarianborn British writer and jounalist. November 12, 2021 Zeyuan Zhu 48 5. Conclusion and Practical Use 創(chuàng)新如高山 山， 快馬加鞭未下鞍。π]（ 或任意一個(gè)跨度為 π的區(qū)間 ） ， Samp。π] (or any span of π), Samp。I程序比 Damp。I program runs approx five times faster than Damp。C大大簡單化 ， C++程序語言實(shí)現(xiàn)Samp。 November 12, 2021 Zeyuan Zhu 43 5. Conclusion and Practical Use It is much easier to code Samp。C algorithm, but some overwhelming advantages of implementing Samp。I algorithm remain linear – O(n) running time. Usually we use q
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1