算法合集之〔半平面交的新算法及其实用价值〕.ppt

Zeyuan Zhu 理论的争议 All great ideas are controversial, or have been at one time. 伟大的理论都是有争议的，或者至少曾经是有争议的。 Gilbert Seldes (1893-1970) U.S. theater, film, and radio critic. 制造机会 A wise man will make more opportunities than he finds. 聪明人总是制造更多的机会，而不是去等待寻找。 Francis Bacon (1561-1626) English philosopher, statesman, and lawyer. 忘记过去，揭开本来面目 After the leaves have fallen, we return to a plain sense of things. It is as if we had come to an end of the imagination. 叶落时分，我们回到一切的本来面目，这样就与创造与幻想的终点不远了。 Wallace Stevens (1879-1955) U.S. poet 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. New algorithm for Half-plane Intersection and its Practical Value–– Thesis for Chinese Team Selecting Contest 2006 半平面交的新算法及其实用价值–– 中国代表队2006年选拔赛论文 Zeyuan Zhu, Grade 12, Nanjing Foreign Language School, Jiangsu, China. 朱泽园, 高三, 南京市外国语学校, 江苏, 中国 Project Overview – 全文总揽 Aim: Present a new O(nlogn) algorithm for half-plane intersection (abbr. HPI), which is one of the most heatedly discussed problems in computer science; emphasize its advantages in practical application, and to some extent, reduce the complexity to O(n). However, the new algorithm will be extraordinarily easy to be implemented. Project Overview – 全文总揽 §1 introduces what Half-Plane Intersection (HPI) is. 什么是半平面交. §2 prepares a convex polygon intersection (CPI). 凸多边形交预备知识. §3 briefly discuss a common solution for HPI – DC. 简要介绍旧DC算法. §4 my new algorithm SI emerges detailedly. 揭开我的新算法SI神秘面纱. §5 conclusion and discussion on further practical use. 总结和实际运用. 1. Statement of the Problem - 问题概述 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 half-plane (also named h-plane for short) as one side of this line. 1. Statement of the Problem Given n half-planes, aix+biy?ci (1?i?n), you are to determine the set of all points