Computing the arrangement of curve segments: Divide-and-conquer algorithms via sampling

We describe two deterministic algorithms for constructing the arrangement determined by a set of (algebraic) curve segments in the plane. They both use a divide-and-conquer approach based on derandomized geometric sampling and achieve the optimal running time O(n log n+k), where n is the number of segments and k is the number of intersections. The first algorithm, a simplified version of one presented in [1], generates a structure of size O(n log log n+k) and its parallel implementation runs in time O(log² n). The second algorithm is better in that the decomposition of the arrangement constructed has optimal size O(n+k) and it has a parallel implementation in the EREW PRAM model that runs in time O(log^3/2 n). The improvements in the second algorithm are achieved by means of an approach that adds some degree of globality to the divide-and-conquer approach based on random sampling. The approach extends previous work by Dehne et al., Deng and Zhu and Kuehn, that use small separators for planar graphs in the design of randomized geometric algorithms for coarse grained multicomputers. The approach simplifies other previous geometric algorithms, and also has the potential of providing efficient deterministic algorithms for the external memory model.