Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification

This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speed up the process. As result, simplified models completely free of topologically inconsistent results and round-off errors due to the use of multiple precision rational numbers. In addition, there was a considerable speedup arising from the use of parallel computing.