Parallelizing 2D-Convex Hulls on clusters: Sorting matters

Abstract

This article explores three basic approaches to parallelize the planar Convex Hull on computer clusters. Methods which are based on sorting the points are found to be inadequate for computer clusters due to the communication costs involved.