Line Simplification (Line Simplification)

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