An Optimal Online Algorithm for Half Plane Intersection

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 structur…