An Optimal Online Algorithm for Halfplane Intersection

来源 :计算机科学技术学报(英文版) | 被引量 : 0次 | 上传用户:liongliong539
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
The intersection of N halfplanes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). In this paper, an optimal online algorithm which runs also in time O(N log N) for this problem is presented. The main idea of the algorithm is to give a new definition for the left side of a given line, to assign the order for the points of a convex polygon, and then to use binary search method in an ordered vertex set. The data structure used in the algorithm is no more complex than array.
其他文献
位于湖北省宜昌市夷陵区的百里荒,以广袤无垠的草原和奇特的自然风光闻名于世。这里曾是国家南方草场建设北羊南养的科研实验基地,得天独厚的自然资源,决定了这里非常适合发展养
期刊
期刊
该文从挂篮荷载计算、施工流程、支座及临时固结施工、挂篮安装及试验、合拢段施工、模板制作安装、钢筋安装、混凝土的浇筑及养生、测量监控等方面人手,介绍了S226海滨大桥
编者按:针对当前生猪低速,养猪又陷入大面积亏损的形势,4月1日晚间,农业部有关负责人就猪市短期的市场形势以及如何稳定生猪生产进行了答记者问.rn问:目前多数地区生猪养殖已
小程序是微信体系中继公众号后,下一个红利风口.如何抓住小程序红利,许多人卡在小程序风控尺度问题,想做小程序,又怕做起规模被微信封杀,稍微有点规模就战战兢兢,这样技术投
期刊
人才始终是核心,今后还需不遗余力rn各地电商扶贫面临的困难很多,一些困难不尽相同,但总体上都会遇到一个共同的大问题,就是人才瓶颈,能懂的人很少,会干的人更少,能干好的更
期刊
作为“中国名茶之乡”、“全国特色产茶县”、“全国重点产茶县”,湖北省谷城县一直把茶叶产业作为农业的主导产业来抓。为提升茶叶品质,打响茶叶品牌知名度,积极倡导有机化生产
目的探究糖尿病足护理单联合针对性护理干预对糖尿病足患者的影响效果。方法选取该院2017年3月—2018年3月收治的100例糖尿病足患者进行研究,均等分组后,监测两组患者治疗前
本文通过对荣华二采区10
期刊