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

Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos

Research output: Contribution to conferencePaperpeer-review


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(log2 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(log3/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.

Original languageEnglish (US)
Number of pages2
StatePublished - 2000
Externally publishedYes
Event11th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, USA
Duration: Jan 9 2000Jan 11 2000


Other11th Annual ACM-SIAM Symposium on Discrete Algorithms
CitySan Francisco, CA, USA

ASJC Scopus subject areas

  • Software
  • General Mathematics


Dive into the research topics of 'Computing the arrangement of curve segments: Divide-and-conquer algorithms via sampling'. Together they form a unique fingerprint.

Cite this