Optimal parallel algorithms for point-set and polygon problems |
| |
Authors: | Richard Cole Michael T Goodrich |
| |
Affiliation: | 1. Courant Institute, New York University, 10012, New York, NY, USA 2. Department of Computer Science, The Johns Hopkins University, 21218, Baltimore, MD, USA
|
| |
Abstract: | In this paper we give parallel algorithms for a number of problems defined on point sets and polygons. All our algorithms have optimalT(n) * P(n) products, whereT(n) is the time complexity andP(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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|