Line Simplification with Restricted Orientations

Line Simplification with Restricted Orientations

We study the C-oriented 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 e, we search for a ``C-oriented'' polygonal chain Q consisting of the minimum number of line segments that has distance at most e to P in the Frechet metric. A polygonal chain is C-oriented 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 e formed around adjacent vertices of the polygonal chain do not intersect. We solve the C-oriented 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(kn^2 log(n)) where k is the minimum number of line segments of Q and uses O(kn^2) space.