Line simplification with restricted orientations
Gabriele Neyer · Repository for Publications and Research Data (ETH Zurich) · 1998
We study the line simplification problem: Given a polygonal chain P represented by an ordered set of vertices p1. . . . pn in the plane, a set of orientations C, and a constant Ɛ, we search for a C-oriented polygonal chain Q consisting of the minimum number of line segments that has distance at most Ɛ to P in the FrEchet metric. A polygonal chain is if the line segments are parallel to orientations in C. We restrict our attention to the version of the problem where two circles of radius Ɛ formed around adjacent vertices of the polygonal chain do not intersect. We solve the line simplification problem constructively by using dynamic programming together with a nice data structure. For usual cases of C our algorithm solves the problem in time O(kn2 log(n)) where k is the minimum number of line segments of Q and uses O(kn2) space.