**Project Description: ** | Line simplification is a process of reducing the number of line segments and vertices to
represent a polyline. This reduction in the number of line segments and vertices can improve the
performance of spatial analysis applications. The classic Douglas-Peucker algorithm developed
in 1973 has a complexity of O(mn), where n denotes the number of vertices and m the number of
line segments. Its enhanced version proposed in 1992 has a complexity of O(n log n). In this
report, we present a parallel line simplification algorithm using a parallel Multiple-instructionstream
Associative Computing model (MASC). Using one instruction stream of the MASC
model, our algorithm has a parallel complexity of O(n) in the worst case using n processing
elements. The parallel algorithm is implemented using Chapel, a parallel programming language
being developed by Cray Inc. The performance of the parallel program was then evaluated on
different parallel computers. |