Heuristic algorithms are fast, but they cannot provide optimal solution. Optimal algorithms of complexity O(N2)–O(N3) are too slow to be used for large input. As it was already noticed by Heckbert and Garland who wrote [101]: "Optimal simplification typically has quadratic or cubic cost, making it impractical for large inputs". Zhang and Guo [312] also wrote that, in practice, the vertices number of a curve which DP or other exact optimal methods can tackle is about a 100 points. They have not provided information concerning processing time for test shapes they used. Nevertheless, the note is symptomatic: time complexity of optimal algorithms is high. Understanding that fact, the authors of optimal methods have also proposed a number of approaches to reduce processing time at the cost of optimality.
Perez and Vidal [194] in their concluding remarks have mentioned two possible techniques for obtaining controlled reduction in computational cost. The one is beam search, which essentially consists of discarding those branches that lead to an error greater than a certain margin at any given stage. The other method is to apply adjustment window that limits the maximum and minimum number of points assigned to any given edge.
Haugland et al. [97] motivates the development of optimal algorithms that the optimal algorithms can serve as a powerful tool when analyzing possible heuristic algorithms. He proposes the following approaches for further studies: a) divide the samples into K parts and perform processing on each of these; the execution time is reduced by about K2; b) start with the path involving the first and last vertices only, and augment it gradually by one vertex until an M-vertex path is achieved; c) start with an arbitrary path with M segments and change the vertices on the path successively so that the path length is gradually reduced. Haugland et al. developed algorithm for approximation of ECG signals. In the case of quasi-periodical ECG signals, this approach is quite satisfactory, but in the case of arbitrary planar (or space) curve it can cause significant lost of quality.
Mori et al. [171] presented algorithm for optimal approximation of curves by linear segments, arcs and splines proposed 5:1 decimation of curve vertices to reduce processing time. Schroeder and Laurent [243] proposed following two-step scheme for min-# problem: reduce the number of vertices using the approximation algorithm with bigger value of error tolerance r e, where r >1, and apply the approximation algorithm to the obtained curve with a given error tolerance e.
Salotti [230, 231] used preliminary approximation of the input to get upper limit for the approximation error to be used further in the process of the state space exploration. He also introduced two heuristic functions for cost function estimation to reduce the search. His A*-search algorithm is optimal but the complexity is still O(N2) even in the best case.
Optimal algorithms are slow, whereas heuristic algorithms are fast but they lack the optimality. There have been attempts to improve the quality of heuristic algorithms by using local search or stochastic optimization techniques (see vertex-adjustment methods), but these methods cannot guarantee optimality or high fidelity. On the other hand, there have been attempts to reduce the processing time of DP algorithms by cost of optimality.
Polygonal approximation which is very close to the optimal one, is quite enough in most practical applications, because the real accuracy of output polygonal approximation is defined by the following factors: a) fidelity of the approximation algorithm, and b) accuracy of input vertex data (digitized curves, vector map). The quest for 100% fidelity is justified from mathematical point of view, but this demand can be released in practical applications if we take into consideration all technical details of the application and the time cost of the optimal result.
In P4 , we try to bridge the gap between the optimal and heuristic algorithms by introducing a new paradigm of bounding corridor in the state space. Instead of time-consuming search in the full state space (see Fig. 3.4.1), we offer to perform the search only in the most relevant part of it, bounded by a corridor (see Fig. 3.4.2).
Figure 3.4.1: Illustration of the modified single-goal state space W for a sample problem size of N=35, M=13. The start and goal states are marked with the gray squares.
Figure 3.4.2: Illustration of the bounding corridor of width W=3 in the state space W . The reference path H is marked by the gray circles; the single-goal state space W is marked by the dashed line.
Figure 3.4.3: Illustration of the multiple-goal bounding corridor of width W=3 in the state space W . The reference path H is marked by the gray circles; the multiple-goal state space W is marked by the dashed line.
The corridor of fixed width W in the state space is constructed along a reference path, which can be obtained by any fast heuristic algorithm.
In contrast to constraints on approximation error [230, 231], we use geometrical constraints on search area in the state space to control the breadth of the search. Width of the corridor W at some approximation point defines the range of possible numbers of approximation segments for the point. At the same time, location of the approximation points is optimized too. In the mentioned algorithms with local adjustment of approximation points the number of segments assigned to curve part from the first vertex to approximation point is the same, only the location of the approximation point can be changed within a narrow range.
The optimization algorithms [44, 153, 173, 110] can be formally considered as a special case of the search in narrow non-continuous corridor. On the other hand, the reduced search algorithm with reference approximation can be treated as optimization of the preliminary (reference) solution. The main difference of the reduced search algorithm from the vertex adjustment method is not only quantitative (wider range of the search), but it is qualitative one too. The introduced paradigm of bounding corridor allows us to solve a number of approximation problems, which cannot be solved by mentioned above vertex adjustment and search reduction methods because of the following reasons.
a) The proposed reduced search algorithm can be iterated using the output solution as a new reference path in the next iteration. The number of iterations can be given in advance, or adaptively varied depending on the development of the approximation error. With the iterative reduce search we can achieve practically optimal solution in O(N)¸ O(N2) time [P4] . With vertex adjustment method we cannot improve obtained solution by additional iterations.
b) The presented single-goal bounding corridor can be extended to the case of multiple-goal corridor (see Fig. 3.4.3). With the search in the multiple-goal bounding corridor a family of solutions can be obtained, that is defined by the corridor width W. This kind of corridor have been further used for solving the multiple object min-e problem [P7].
c) In the case of min-e problem for closed contours, the corresponding analysis of solutions in the bounding corridor can be performed to find the sub-path with conjugate states that provides minimum of cost function (approximation error). This sub-path gives optimal approximation solution to the closed contour, including optimal selection of the starting point [P6] .
Approximation of locally concave/convex curves
In the section 3.3.2 it was mentioned that matrix search algorithm might be applied to reduce processing time for approximation of locally concave/convex curves. This idea fits perfectly to the reduced search approach. Performing search in the bounding corridor we involve some part of the curve into the computation. If this part is concave (or convex) the search for the minimum, could be speed-up with matrix search algorithm [7, 8, 297, 298]. Information obtained at the first run of reduced search about the location of concave/convex parts could be used in subsequent iterations. Joint using of matrix search algorithm and iterative reduced search approach for locally concave/convex curves to reduce processing time is a topic for future studies.
Later we will use the iterative reduced search for the development of efficient algorithms in polygonal approximation field, namely, min-# problem for open curves, min-e and min-# approximation of closed contours, and min- e approximation of multiple objects.