算法合集之半平面交的新算法及其實(shí)用價(jià)值(已修改)
2025-10-23 20:30 本頁(yè)面
【正文】 November 12, 2021 Zeyuan Zhu 4 Hello, Ladies and Gentlemen. 女士們先生們大家好 Bonjour, Mesdames et Messieurs. Witajcie, Panie i Panowie. Hallo, Damen und Herren. Buna ziua, Doamenelor si Domnilor. Ciao, signore e signori. Zeyuan Zhu, Grade 12, Nanjing Foreign Language School, Jiangsu, China. 朱澤園 , 高三 , 南京市外國(guó)語(yǔ)學(xué)校 , 江蘇 , 中國(guó) November 12, 2021 Zeyuan Zhu 5 New algorithm for Halfplane Intersection and its Practical Value –– Thesis for Chinese Team Selecting Contest 2021 半平面交的新算法及其實(shí)用價(jià)值 –– 中國(guó)代表隊(duì) 2021年選拔賽論文 Zeyuan Zhu, Grade 12, Nanjing Foreign Language School, Jiangsu, China. 朱澤園 , 高三 , 南京市外國(guó)語(yǔ)學(xué)校 , 江蘇 , 中國(guó) November 12, 2021 Zeyuan Zhu 6 Project Overview – 全文總攬 Aim: Present a new O(nlogn) algorithm for halfplane intersection (abbr. HPI), which is one of the most heatedly discussed problems in puter science。 emphasize its advantages in practical application, and to some extent, reduce the plexity to O(n). However, the new algorithm will be extraordinarily easy to be implemented. 主旨 : 半平面的交是當(dāng)今學(xué)術(shù)界熱烈討論的問(wèn)題之一，本文將介紹一個(gè)全新的 O(nlogn)半平面交算法，強(qiáng)調(diào)它在實(shí)際運(yùn)用中的價(jià)值，并且在某種程度上將復(fù)雜度下降至 O(n)線性。最重要的是，我將介紹的算法非常便于實(shí)現(xiàn) . November 12, 2021 Zeyuan Zhu 7 Project Overview – 全文總攬 167。 1 introduces what HalfPlane Intersection (HPI) is. 什么是半平面交 . 167。 2 prepares a convex polygon intersection (CPI). 凸多邊形交預(yù)備知識(shí) . 167。 3 briefly discuss a mon solution for HPI – Damp。C. 簡(jiǎn)要介紹舊 Damp。C算法 . 167。 4 my new algorithm Samp。I emerges detailedly. 揭開(kāi)我的新算法 Samp。I神秘面紗 . 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表示，類(lèi)似地半平面以 ax+by ?(?)c為定義。 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的半平面，找到所有滿(mǎn)足它們的點(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 intersecti
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1