Article ID: | iaor1992668 |
Country: | United Kingdom |
Volume: | 42 |
Issue: | 9 |
Start Page Number: | 793 |
End Page Number: | 802 |
Publication Date: | Sep 1991 |
Journal: | Journal of the Operational Research Society |
Authors: | Campbell Gerard M., Cromley Robert G. |
Keywords: | networks |
Line simplification is a process by which unnecessary detail in cartographic data is eliminated. In the past, a variety of heuristics have been implemented to simplify lines. This paper describes practical algorithms which have been developed to provide optimal solutions. The line simplification problem is shown to have the special structure of an acyclic shortest-path problem. Three formulations are presented, which differ in the form of their objectives and/or constraints, and a solution algorithm is outlined for each formulation. Issues associated with implementation are addressed by using each algorithm to perform various degrees of simplification on a large example line. Possibilities for future research related to optimal line simplification are also discussed.