An algorithm for polygon overlay using cooperative parallel processing

Abstract

With the increasing importance of parallel computing, attention must be given to utilising these resources efficiently. This article describes an algorithm to use cooperating parallel processors to solve the problem of vector polygon overlay, one of the most computationally-intensive problems in the GIS arena. The basic algorithm, which is described here using natural language, is not specific to a particular parallel architecture but has elements that are best suited to particular configurations, namely distributed-memory Multiple Instruction stream Multiple Data stream (MIMD) architectures. The intention is to provide an algorithm which utilises the potential of such architectures by distributing the computational load over several cooperating processors.