Speeding Up the Douglas-Peucker Line-Simplification Algorithm
Generate an AI Snapshot to get a quick, structured summary of this paper.
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
A algorithm is given, based on path hulls, that uses the geometric structure of the problem to attain a worst-case running time proportional to n log_2(n), which is the best case of the Douglas algorithm.
Abstract
We analyze the line simplification algorithm reported by Douglas and Peucker and show that its worst case is quadratic in n, the number of input points. Then we give a algorithm, based on path hulls, that uses the geometric structure of the problem to attain a worst-case running time proportional to n log 2 n, which is the best case of the Douglas algorithm. We give complete C code and compare the two algorithms theoretically, by operation counts, and practically, by machine timings.