Efficient geometric algorithms on the EREW PRAM

Author

Chen, Danny Z.

Author_Institution

Dept. of Comput. Sci. & Eng., Notre Dame Univ., IN, USA

Volume

6

Issue

1

fYear

1995

fDate

1/1/1995 12:00:00 AM

Firstpage

41

Lastpage

47

Abstract

We present a technique that can be used to obtain efficient parallel geometric algorithms in the EREW PRAM computational model. This technique enables us to solve optimally a number of geometric problems in O(log n) time using O(n/log n) EREW PRAM processors, where n is the input size of a problem. These problems include: computing the convex hull of a set of points in the plane that are given sorted, computing the convex hull of a simple polygon, computing the common intersection of half-planes whose slopes are given sorted, finding the kernel of a simple polygon, triangulating a set of points in the plane that are given sorted, triangulating monotone polygons and star-shaped polygons, and computing the all dominating neighbors of a sequence of values. PRAM algorithms for these problems were previously known to be optimal (i.e., in O(log n) time and using O(n/log n) processors) only on the CREW PRAM, which is a stronger model than the EREW PRAM

Keywords

computational complexity; computational geometry; parallel algorithms; random-access storage; CREW PRAM; EREW PRAM; PRAM algorithms; common intersection; computational model; convex hull; geometric algorithms; half-planes; kernel; monotone polygons; parallel geometric algorithms; simple polygon; star-shaped polygons; triangulating; Algorithm design and analysis; Computational geometry; Computational modeling; Concurrent computing; Kernel; Parallel algorithms; Phase change random access memory; Read-write memory; Solid modeling; Time sharing computer systems;

fLanguage

English

Journal_Title

Parallel and Distributed Systems, IEEE Transactions on

Publisher

ieee

ISSN

1045-9219

Type

jour

DOI

10.1109/71.363412

Filename

363412