Computing homotopic line simplification

In this paper, we study a variant of the well-known line-simplification problem. For this problem, we are given a polygonal path P=p1,p2,…,pnP=p1,p2,…,pn and a set SS of m   point obstacles in the plane, with the goal being to determine an optimal homotopic simplification of PP. This means finding a minimum subsequence Q=q1,q2,…,qkQ=q1,q2,…,qk (q1=p1q1=p1 and qk=pnqk=pn) of PP that approximates PP within a given error ε   that is also homotopic to PP. In this context, the error is defined under a distance function that can be a Hausdorff or Fréchet distance function, sometimes referred to as the error measure. In this paper, we present the first polynomial-time algorithm that computes an optimal homotopic simplification of PP in O(n6m2)+TF(n)O(n6m2)+TF(n) time, where TF(n)TF(n) is the time to compute all shortcuts pipjpipj with errors of at most ε under the error measure F  . Moreover, we define a new concept of strongly homotopic simplification where every link qlql+1qlql+1 of QQ corresponding to the shortcut pipjpipj of PP is homotopic to the sub-path pi,…,pjpi,…,pj. We present a method that in O(n(m+n)log(n+m))O(n(m+n)log(n+m)) time identifies all such shortcuts. If PP is x  -monotone, we show that this problem can be solved in O(mlog(n+m)+nlognlog(n+m)+k) time, where k is the number of such shortcuts. We can use Imai and Iri's framework [24] to obtain the simplification at the additional cost of TF(n)TF(n).