Computing the arrangement of curve segments: divide-and-conquer algorithms via sampling
Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos · 2000
Random sampling provides a natural approach for computing the arrangement of a set of geometric objects via divide-and-conquer. Unfortunately, in many cases it does not lead to an optimal algorithm. We show that in the case of the arrangement of n (algebraic) curve segments in the plane, the resulting algorithm has a running time that is asymptotically optimal, namely O(n log n + k), where k is the number of pairwise intersections between the segments. We also introduce a new general approach, divide-and-conquer with partial clean-up, that adds certain globality to the plain divide-and-conquer approach. We apply this approach to the segments problem and obtain a second algorithm that constructs a structure of optimal size O(n+k), in contrast to O(n log log n+k) for the rst algorithm in this paper and a previous one [8] (this previous algorithm also had the drawback of handling only line segments). The second algorithm also results in an ecient deterministic algorithm for co...