# Line Simplification (Line Simplification)

Jump to navigation
Jump to search

## Description

Line simplification is the process of taking a line/curve as represented by a list of points and reducing the number of points needed to accurately represent the given line.

## Parameters

$n$: number of points representing the curve/line initially

## Table of Algorithms

Name | Year | Time | Space | Approximation Factor | Model | Reference |
---|---|---|---|---|---|---|

Ramer–Douglas–Peucker algorithm | 1972 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time |

Visvalingam–Whyatt | 1993 | $O(n^{2})$ | $O(n)$ | Exact | Deterministic | Time |

Reumann–Witkam | 1974 | $O(n)$ | $O({1})$ | Exact | Deterministic | |

Opheim simplification | 1981 | $O(n)$ | $O({1})$ | Exact | Deterministic | Time |

Lang simplification | 1969 | $O(n)$ | $O({1})$ | Exact | Deterministic | |

Zhao-Saalfeld | 1997 | $O(n)$ | $O(n)$ | Exact | Deterministic | Time |