Daneshpajou, Shervin^{1}; Abam, Mohammad^{1}; Deleuran, Lasse Kosetski^{4}; Ghodsi, Mohammad^{3}

Affiliations:

^{1} Department of Computer Science, Faculty of Science, Aarhus University, Aarhus University^{2} Department of Computer Science, Science and Technology, Aarhus University^{3} unknown^{4} Department of Computer Science, Science and Technology, Aarhus University

Abstract:

We study a variant of the line-simplification problem where we are given a polygonal path P = p1 , p2 , . . . , pn and a set S of m point obstacles in a plane, and the goal is to find the optimal homotopic simplification, that is, a minimum subsequence Q = q1 , q2 , . . . , qk (q1 = p1 and qk = pn ) of P defining a polygonal path which approximates P within the given error ε and is homotopic to P . We assume all shortcuts pi,pj whose errors under a distance function F are at most ε can be computed in TF(n) time where TF(n) is polynomial for all widely-used distance functions. We define the new concept of strongly homotopic simplification where every link ql,ql+1 of a simplification Q corresponding to the shortcut pi,pj of a given path P is homotopic to the sub-path pi , . . . , pj of P . We present a general method running in time O(n(m + n) log(nm)) for identifying every shortcut pi,pj that is homotopic to the sub-path pi , . . . , pj of P , called a homotopic shortcut. In the case of x-monotone paths we propose an efficient and simple method to compute all homotopic shortcuts in O(m log(nm) + n log n log(nm) + k) time where k is the number of homotopic shortcuts. Under any desired measure F , both methods can be simply combined with Imai and Iri’s framework to obtain the optimal strongly-homotopic simplification in O(n(m + n) log(nm)) + TF (n) and O(m log(nm) + n log n log(nm) + k) + TF (n) time for general paths and x-monotone paths respectively