×

Parallel implementations for determining the 2D convex hull. (English) Zbl 0903.68086

Summary: A number of related factors determine whether the ideal offered by parallel processing of a linear increase in performance with an increased number of processors is approached. It is vital to understand the nature of the application being ‘parallelized’ so that each factor can be considered for that application to determine if it is suitable for parallelization. This paper demonstrates the value of analyzing a serial implementation as part of understanding the application’s nature. It also describes a parallel implementation of a divide-and-conquer parallel algorithm for determining the convex hull of a set of 2D points, following an earlier serial implementation. It is compared with an earlier parallelization of the serial divide-and-conquer Preparata-Hong algorithm. It analyses the algorithms and determines the factors affecting their parallelization.

MSC:

68W10 Parallel algorithms in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI