1
$\begingroup$

This question is inspired by a lossy compression technique for polylines, namely to identify a subset of the points of polyline $\mathcal{P}$, whose removal yields a polyline $\mathcal{Q}$ within a given Hausdorff distance of $\mathcal{P}$.
The primary objective of this "weeding" is to obtain $\mathcal{Q}$ with minimal number of points. The most prominent heuristic is the Ramer-Douglas-Peucker algorithm and I do not know of any exact algorithm.

Question:
given a polyline $\mathcal{P}$ with $n>2$ points, is there an algorithm or formulation of the optimization problem, that yields among all polylines $\mathcal{Q}$ with $d_H\left(\mathcal{P},\mathcal{Q}\right)\le c$ one of those with a minimal number of points?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

The paper below is close to your question, but not exactly. I don't think your exact question has been answered in the literature. This paper finds the optimal simplification under the Hausdorff measure for monotone polygonal chains. They get further with the Fréchet distance, without the monotone restriction. They also compare experimentally against Douglas-Peucker (DP below).

P. K. Agarwal and S. Har-Peled and N. H. Mustafa and Y. Wang. Near-linear time approximation algorithms for curve simplification. Proc. of the 10th Annual European Symp. on Algorithms, 29-41, 2005. PDF download.

Simplifications

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .