ISSN:
1432-0541
Keywords:
Computational geometry
;
Parallel algorithms
;
Polygon
;
All nearest-neighbor problem
;
Kernel problem
;
Convex hull
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01758749
