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

Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
**Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification.**
*RBC. Revista Brasileira de Cartografia (Online)*, 68:1221–1230, 2016.
online at \url http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857.

[full text]
[BibTeX▼]

## Abstract

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.

## Full Text

[download]