Sweeping Algorithm for Triangulation of Plane Point-Line Set

Sweeping algorithm is presented for the triangulation of plane point-line set. The algorithm makes use of the idea of plane sweeping. When the sweep-line reaches it, the event-point will be dealt with, viz., the event-point is connected with some points swept and thus the swept regions are triangulated. When the sweep-line reaches the leftmost event-point, the point will be dealt with, and the triangulation of the plane point-line set is accomplished. It is proved in detail that the time complexities of the algorithm is O(NlbN), where N is the sum of the number of points and the number of line-segment endpoints within the point-line set.