算法合集之半平面交的新算法及其實(shí)用價(jià)值(完整版)
【正文】 。 。 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é)競(jìng)賽 創(chuàng)新與技術(shù) 我心目中的創(chuàng)新 ——最重要的是 思想創(chuàng)新 ， 其次是 行為 創(chuàng)新 ， 再其次是文章創(chuàng)新 ， 再再其次才是語(yǔ)言創(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)新如高山 山， 快馬加鞭未下鞍。π] (or any span of π), Samp。I program runs approx five times faster than Damp。 November 12, 2021 Zeyuan Zhu 43 5. Conclusion and Practical Use It is much easier to code Samp。I algorithm remain linear – O(n) running time. Usually we use quicksort. The total plexity is O(nlogn), with fairly small constant factor hidden. ? 除了 Step2中的排序以外， Samp。π, 189。π]給出上半個(gè)， (π, 189。π, 189。π, 189。I 我自創(chuàng)的排序增量算法 November 12, 2021 Zeyuan Zhu 25 4. SortandIncremental Algorithm ? Definition of hplane’ s polar angle: for hplane like xy?constant, we define its polar angle to 188。 November 12, 2021 Zeyuan Zhu 10 1. Statement of the Problem Given n halfplanes, aix+biy?ci (1?i?n), you are to determine the set of all points that satisfying all the n inequations. 給定 n個(gè)形如 aix+biy?ci的半平面，找到所有滿足它們的點(diǎn)所組成的點(diǎn)集 November 12, 2021 Zeyuan Zhu 11 1. Statement of the Problem Feasible region forms a shape of convex hull possibly unbounded. Add four hplanes forming a rectangle, to make the intersection area finite. 合并后區(qū)域形如凸多邊形，可能無(wú)界 此時(shí)增加 4個(gè)半平面保證面積有限 November 12, 2021 Zeyuan Zhu 13 1. Statement of the Problem Pay attention that intersection sometimes yields a line, a ray, a linesegment, a point or an empty region. 注意相交后的區(qū)域，有可能是一個(gè)直線、射線、線段或者點(diǎn)，當(dāng)然也可能是空集。 2 prepares a convex polygon intersection (CPI). 凸多邊形交預(yù)備知識(shí) . 167。 1 introduces what HalfPlane Intersection (HPI) is. 什么是半平面交 . 167。 5 conclusion and discussion on further practical use. 總結(jié)和實(shí)際運(yùn)用 . November 12, 2021 Zeyuan Zhu 8 1. Statement of the Problem 問(wèn)題概述 November 12, 2021 Zeyuan Zhu 9 1. Statement of the Problem A line in plane is usually represented as ax+by=c. Similarly, its inequality form ax+by ?(?) c represents a halfplane (also named hplane for short) as one side of this line. 3x2y=1 x+2y?1 眾所周知，直線常用 ax+by=c表示，類似地半平面以 ax+by ?(?)c為定義。 2 分 : 將 n個(gè)半平面分成兩個(gè) n/2的集合 . 治 : 對(duì)兩子集合遞歸
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1