Computing homotopic line simplification (Q2249045)

The following problem is investigated: Let \(\mathcal{P}=p_1,p_2,\dots,p_n\) a given polygonal path and \(\mathcal{S}=\{s_1,s_2,\dots,s_m\}\) a set of \(m\) point obstacles in the plane not intersecting \(\mathcal{P}\), and \(\epsilon\) an error defined under a distance function \(F\). The problem is to simplify the path \(\mathcal{P}\) by \(\mathcal{Q}=q_1,q_2,\dots,q_k\) \((q_1=p_1,)\) and \(q_k=p_n\) within the given error \(\epsilon\) so that \(\mathcal{Q}\) is homotopic to \(\mathcal{P}\). The first polynomial-time algorithm computes an optimal homotopic simplification of \(\mathcal{P}\) in \(O(n^6m^2)+T_F(n)\) time, where \(T_F(n)\) is the time to compute all shortcuts \(p_ip_j\) with error of at most \(\epsilon\) under the error measure \(F\). A method is presented that identifies all such shortcuts in \(O(n(m+n)\log(n+m))\) time.