### Abstract

Techniques are presented for parallel divide-and-conquer, resulting in improved parallel algorithms for a number of problems, including intersection detection, trapezoidal decomposition (hence, polygon triangulation), and planar point location (hence, Voronoi diagram construction). Efficient parallel algorithms are also given for fractional cascading, three-dimensional maxima, two-set dominance counting, and visibility from a point. All of the algorithms run in O(log n) time with either a linear or sublinear number of processors in the concurrent-read-exclusive-write parallel random-access machine model.

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

Title of host publication | Annual Symposium on Foundations of Computer Science (Proceedings) |

Publisher | IEEE |

Pages | 151-160 |

Number of pages | 10 |

ISBN (Print) | 0818608072, 9780818608070 |

DOIs | |

State | Published - 1987 |

### Publication series

Name | Annual Symposium on Foundations of Computer Science (Proceedings) |
---|---|

ISSN (Print) | 0272-5428 |

### ASJC Scopus subject areas

- Hardware and Architecture

## Fingerprint Dive into the research topics of 'CASCADING DIVIDE-AND-CONQUER: A TECHNIQUE FOR DESIGNING PARALLEL ALGORITHMS.'. Together they form a unique fingerprint.

## Cite this

*Annual Symposium on Foundations of Computer Science (Proceedings)*(pp. 151-160). (Annual Symposium on Foundations of Computer Science (Proceedings)). IEEE. https://doi.org/10.1109/sfcs.1987.12