### Abstract

In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimal T(n) * P(n) products, where T(n) is the time complexity and P(n) is the number of processors used, and are for the EREW PRAM or CREW PRAM models. Our algorithms provide parallel analogues to well-known phenomena from sequential computational geometry, such as the fact that problems for polygons can oftentimes be solved more efficiently than point-set problems, and that nearest-neighbor problems can be solved without explicitly constructing a Voronoi diagram.

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

Pages (from-to) | 3-23 |

Number of pages | 21 |

Journal | Algorithmica (New York) |

Volume | 7 |

Issue number | 1 |

DOIs | |

State | Published - 1992 |

### Keywords

- All nearest-neighbor problem
- Computational geometry
- Convex hull
- Kernel problem
- Parallel algorithms
- Polygon

### ASJC Scopus subject areas

- Computer Graphics and Computer-Aided Design
- Software
- Safety, Risk, Reliability and Quality
- Applied Mathematics

## Fingerprint Dive into the research topics of 'Optimal parallel algorithms for point-set and polygon problems'. Together they form a unique fingerprint.

## Cite this

Cole, R., & Goodrich, M. T. (1992). Optimal parallel algorithms for point-set and polygon problems.

*Algorithmica (New York)*,*7*(1), 3-23. https://doi.org/10.1007/BF01758749