An optimal online algorithm for halfplane intersection |
| |
Authors: | Jigang Wu Yongchang Ji Guoliang Chen |
| |
Affiliation: | (1) Department of Computer Science, Yantai University, 264005 Yantai, P.R. China;(2) Department of Computer Science and Technology, University of Science and Technology of China, 230026 Hefei, P.R. China;(3) National High Performance Computing Center, University of Science and Technology of China, 230026 Hefei, P.R. China |
| |
Abstract: | The intersection of N half Planes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). ln 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. |
| |
Keywords: | computational geometry intersection of halfplanes online algorithm complexity |
本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录! |
| 点击此处可从《计算机科学技术学报》浏览原始摘要信息 |
|
点击此处可从《计算机科学技术学报》下载免费的PDF全文 |