算法合集之半平面交的新算法及其實用價值(已修改)
2024-10-28 20:30 本頁面
【正文】 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. 朱澤園 , 高三 , 南京市外國語學(xué)校 , 江蘇 , 中國 November 12, 2021 Zeyuan Zhu 5 New algorithm for Halfplane Intersection and its Practical Value –– Thesis for Chinese Team Selecting Contest 2021 半平面交的新算法及其實用價值 –– 中國代表隊 2021年選拔賽論文 Zeyuan Zhu, Grade 12, Nanjing Foreign Language School, Jiangsu, China. 朱澤園 , 高三 , 南京市外國語學(xué)校 , 江蘇 , 中國 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ù)界熱烈討論的問題之一，本文將介紹一個全新的 O(nlogn)半平面交算法，強調(diào)它在實際運用中的價值，并且在某種程度上將復(fù)雜度下降至 O(n)線性。最重要的是，我將介紹的算法非常便于實現(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ù)備知識 . 167。 3 briefly discuss a mon solution for HPI – Damp。C. 簡要介紹舊 Damp。C算法 . 167。 4 my new algorithm Samp。I emerges detailedly. 揭開我的新算法 Samp。I神秘面紗 . 167。 5 conclusion and discussion on further practical use. 總結(jié)和實際運用 . November 12, 2021 Zeyuan Zhu 8 1. Statement of the Problem 問題概述 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為定義。 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個形如 aix+biy?ci的半平面，找到所有滿足它們的點所組成的點集 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ū)域形如凸多邊形，可能無界 此時增加 4個半平面保證面積有限 November 12, 2021 Zeyuan Zhu 13 1. Statement of the Problem Pay attention that intersecti
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1