算法合集之《半平面交的新算法及其实用价值》

《算法合集之《半平面交的新算法及其实用价值》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Allgreatideasarecontroversial,orhavebeenatonetime.伟大的理论都是有争议的，或者至少曾经是有争议的。GilbertSeldes(1893-1970)U.S.theater,film,andradiocritic.理论的争议8/23/20211ZeyuanZhuAwisemanwillmakemoreopportunitiesthanhefinds.聪明人总是制造更多的机会，而不是去等待寻找。FrancisBacon(1561-1626)Englishphilosopher,statesman,andlaw

2、yer.制造机会8/23/20212ZeyuanZhuAftertheleaveshavefallen,wereturntoaplainsenseofthings.Itisasifwehadcometoanendoftheimagination.叶落时分，我们回到一切的本来面目，这样就与创造与幻想的终点不远了。WallaceStevens(1879-1955)U.S.poet忘记过去，揭开本来面目8/23/20213ZeyuanZhuHello,LadiesandGentlemen.女士们先生们大家好Bonjour,MesdamesetMessieur

3、s.Witajcie,PanieiPanowie.Hallo,DamenundHerren.Bunaziua,DoamenelorsiDomnilor.Ciao,signoreesignori.ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.朱泽园,高三,南京市外国语学校,江苏,中国8/23/20214ZeyuanZhuNewalgorithmforHalf-planeIntersectionanditsPracticalValue––ThesisforChineseTeamSe

4、lectingContest2006半平面交的新算法及其实用价值––中国代表队2006年选拔赛论文ZeyuanZhu,Grade12,NanjingForeignLanguageSchool,Jiangsu,China.朱泽园,高三,南京市外国语学校,江苏,中国8/23/20215ZeyuanZhuProjectOverview–全文总揽Aim:PresentanewO(nlogn)algorithmforhalf-planeintersection(abbr.HPI),whichisoneofthemostheatedlydiscussedprobl

5、emsincomputerscience;emphasizeitsadvantagesinpracticalapplication,andtosomeextent,reducethecomplexitytoO(n).However,thenewalgorithmwillbeextraordinarilyeasytobeimplemented.主旨:半平面的交是当今学术界热烈讨论的问题之一，本文将介绍一个全新的O(nlogn)半平面交算法，强调它在实际运用中的价值，并且在某种程度上将复杂度下降至O(n)线性。最重要的是，我将介绍的算法非常便于实现.8/2

6、3/20216ZeyuanZhuProjectOverview–全文总揽§1introduceswhatHalf-PlaneIntersection(HPI)is.什么是半平面交.§2preparesaconvexpolygonintersection(CPI).凸多边形交预备知识.§3brieflydiscussacommonsolutionforHPI–D&C.简要介绍旧D&C算法.§4mynewalgorithmS&Iemergesdetailedly.揭开我的新算法S&I神秘面纱.§5conclusionanddiscussiononfurth

7、erpracticaluse.总结和实际运用.8/23/20217ZeyuanZhu1.StatementoftheProblem-问题概述8/23/20218ZeyuanZhu1.StatementoftheProblemAlineinplaneisusuallyrepresentedasax+by=c.Similarly,itsinequalityformax+by()crepresentsahalf-plane(alsonamedh-planeforshort)asonesideofthisline.3x-2y=1x+2y1众所周知，直线常

8、用ax+by=c表示，类似地半平面以ax+by()c为定义。8/23/20219Zeyua