### Abstract

We describe randomized parallel CREW PRAM algorithms for building trapezoidal diagrams of line segments in the plane. For general segments, we give an algorithm requiring optimal O(A + nlogn) expected work and optimal O(logn) time, where A is the number of intersecting pairs of segments. If the segments form a simple chain, we give an algorithm requiring optimal O(n) expected work and O(log n log log ra log^{∗} n) expected time, and a simpler algorithm requiring O(n log^{∗} n) expected work. The serial algorithm corresponding to the latter is the simplest known algorithm requiring O(n log^{∗} n) expected operations. For a set of segments forming K chains, we give an algorithm requiring O(A + n log^{∗} n + K log n) expected work and O(log n log log n log^{∗} n) expected time. The parallel time bounds require the assumption that enough processors are available, with processor allocations every log n steps.

Original language | English (US) |
---|---|

Title of host publication | Proceedings of the Annual Symposium on Computational Geometry |

Publisher | Association for Computing Machinery |

Pages | 152-161 |

Number of pages | 10 |

ISBN (Print) | 0897914260 |

DOIs | |

State | Published - Jun 1 1991 |

Event | 7th Annual Symposium on Computational Geometry, SCG 1991 - North Conway, United States Duration: Jun 10 1991 → Jun 12 1991 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 7th Annual Symposium on Computational Geometry, SCG 1991 |
---|---|

Country | United States |

City | North Conway |

Period | 6/10/91 → 6/12/91 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Randomized parallel algorithms for trapezoidal diagrams'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the Annual Symposium on Computational Geometry*(pp. 152-161). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/109648.109665