Optimal polygonal approximation of digitized curves using the sum of square deviations criterion

We address the problem of finding an optimal polygonal approximation of digitized curves. Several optimal algorithms have already been proposed to determine the minimum number of points that define a polygonal approximation of the curve, with respect to a criterion error. We present a new algorithm with reasonable complexity to determine the optimal polygonal approximation using the mean square error norm. The idea is to estimate the remaining number of segments and to integrate the cost in the A^* algorithm. The solution is optimal in the minimum number of segments.     

An efficient evolutionary algorithm for accurate polygonal approximation

An optimization problem for polygonal approximation of 2-D shapes is investigated in this paper. The optimization problem for a digital contour of N points with the approximating polygon of K vertices has a search space of C(N, K) instances, i.e., the number of ways of choosing K vertices out of N points. A genetic-algorithm-based method has been proposed for determining the optimal polygons of digital curves, and its performance is better than that of several existing methods for the polygonal approximation problems. This paper proposes an efficient evolutionary algorithm (EEA) with a novel orthogonal array crossover for obtaining the optimal solution to the polygonal approximation problem. It is shown empirically that the proposed EEA outperforms the existing genetic-algorithm-based method under the same cost conditions in terms of the quality of the best solution, average solution, variance of solutions, and the convergence speed, especially in solving large polygonal approximation problems.     

遗传算法在曲线多边形近似中的应用

在平面数字曲线的多边形近似中,为克服顶点的检测只依靠部区域,缺 乏全局信息的弱点,文中把多边形近似问题作了寻找在满足一定的近似误差下使顶点数最少,或者使顶点数和近似误差都尽可能少的最优化问题来处理。     

On robotic optimal path planning in polygonal regions with pseudo-Euclidean metrics.

This paper presents several results on some cost-minimizing path problems in polygonal regions. For these types of problems, an approach often used to compute approximate optimal paths is to apply a discrete search algorithm to a graph G(epsilon) constructed from a discretization of the problem; this graph is guaranteed to contain an epsilon-good approximate optimal path, i.e., a path with a cost within (1 + epsilon) factor of that of an optimal path, between given source and destination points. Here, epsilon > 0 is the user-defined error tolerance ratio. We introduce a class of piecewise pseudo-Euclidean optimal path problems that includes several non-Euclidean optimal path problems previously studied and show that the BUSHWHACK algorithm, which was formerly designed for the weighted region optimal path problem, can be generalized to solve any optimal path problem of this class. We also introduce an empirical method called the adaptive discretization method that improves the performance of the approximation algorithms by placing discretization points densely only in areas that may contain optimal paths. It proceeds in multiple iterations, and in each iteration, it varies the approximation parameters and fine tunes the discretization.     

The application of ψ-transform for determining a near-optimal path in the presence of polyhedral obstacles

The problem can be stated as follows: Given a set of simple polyhedra and two points belonging to the exterior domain of the given polyhedra, determine a near-optimal polygonal line connecting the two points so that the intersection of this polygonal line and the given polyhedra is an empty set. To solve this problem an algorithm is formed for generation of a set of admissible polygonal lines. On the basis of this set, using the optimisation procedure based on ψ-transform, a near-optimal polygonal line is determined.     

An application of the self-organizing map in the non-Euclidean Traveling Salesman Problem

An application of the self-organizing map (SOM) to the Traveling Salesman Problem (TSP) has been reported by many researchers, however these approaches are mainly focused on the Euclidean TSP variant. We consider the TSP as a problem formulation for the multi-goal path planning problem in which paths among obstacles have to be found. We apply a simple approximation of the shortest path that seems to be suitable for the SOM adaptation procedure. The approximation is based on a geometrical interpretation of SOM, where weights of neurons represent nodes that are placed in the polygonal domain. The approximation is verified in a set of real problems and experimental results show feasibility of the proposed approach for the SOM based solution of the non-Euclidean TSP.     

Scheduling Independent Multiprocessor Tasks

We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model.     

Scheduling Independent Multiprocessor Tasks

Abstract. We study the problem of scheduling a set of n independent multiprocessor tasks with prespecified processor allocations on a fixed number of processors. We propose a linear time algorithm that finds a schedule of minimum makespan in the preemptive model, and a linear time approximation algorithm that finds a schedule of makespan within a factor of (1+\eps) of optimal in the non-preemptive model. We extend our results by obtaining a polynomial time approximation scheme for the parallel processors variant of the multiprocessor task model.     

Near-Linear Time Approximation Algorithms for Curve Simplification

We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P’ whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P’ while ensuring that the error between P’ and P is below a certain threshold. We consider two different error measures: Hausdorff and Frechet. For both error criteria, we present near-linear time approximation algorithms that, given a parameter ε > 0, compute a simplified polygonal curve P’ whose error is less than ε and size at most the size of an optimal simplified polygonal curve with error ε/2. We consider monotone curves in ℝ² in the case of the Hausdorff error measure under the uniform distance metric and arbitrary curves in any dimension for the Frechet error measure under L_p metrics. We present experimental results demonstrating that our algorithms are simple and fast, and produce close to optimal simplifications in practice.     

Efficient Determination of Four-Point Form-Closure Optimal Constraints of Polygonal Objects

This paper proposes a new and more efficient solution to the problem of determining optimal form-closure constraints of polygonal objects using four contacts. New grasp parameters are determined based only on the directions of the applied forces, which are then used to determine the optimal grasp. Given a set of contact edges, using an analytical procedure a solution that is either the optimal one or is very close to it is obtained (only in this second case an iterative procedure is needed to find a root of a nonlinear equation). This procedure is used for an efficient determination of the optimal grasp on the whole object. The algorithms have been implemented and numerical examples are shown.     

Speeding up simplification of polygonal curves using nested approximations

We develop a top-down multiresolution algorithm (TDMR) to solve iteratively the problem of polygonal curve approximation. This algorithm provides nested polygonal approximations of an input curve. We show theoretically and experimentally that, if the simplification algorithm A{\mathcal{A}} used between any two successive levels of resolution satisfies some conditions, the multiresolution algorithm will have a complexity lower than the complexity of A{\mathcal{A}} applied directly on the input curve to provide the crudest polygonal approximation. In particular, we show that if A{\mathcal{A}} has a O(N ²/K) complexity (the complexity of a reduced search dynamic programming solution approach), where N and K are, respectively, the number of segments in the input curve and the number of segments in the crudest approximation, the complexity of MR is in O(N). We experimentally compare the outcomes of TDMR with those of the optimal full search dynamic programming solution and of classical merge and split approaches. The experimental evaluations confirm the theoretical derivations and show that the proposed approach evaluated on 2D coastal maps either leads to a lower complexity or provides polygonal approximations closer to the initial curves.     

A new measurement for assessing polygonal approximation of curves

This paper presents a novel method for assessing the accuracy of unsupervised polygonal approximation algorithms. This measurement relies on a polygonal approximation called the “reference approximation”. The reference approximation is obtained using the method of Perez and Vidal [11] by an iterative method that optimizes an objective function. Then, the proposed measurement is calculated by comparing the reference approximation with the approximation to be evaluated, taking into account the similarity between the polygonal approximation and the original contour, and penalizing polygonal approximations with an excessive number of points. A comparative experiment by using polygonal approximations obtained with commonly used algorithms showed that the proposed measurement is more efficient than other proposed measurements at comparing polygonal approximations with different number of points.     

Rational L∞-suboptimal controllers for SISOcontinuous-time systems

We study the problem of minimizing the weighted amplitude of the time response due to a given fixed input signal for single-input/single-output (SISO) continuous-time systems and focus on obtaining rational suboptimal solutions. An EAS (Euler approximating system)-based method is proposed for designing a rational L_∞ -suboptimal controller for SISO systems. It is shown that this rational approximation is the best one among a set of rational approximations, in the sense of providing the tightest upper bound and that it can approximate the optimal cost arbitrarily close     

A note on searching line arrangements and applications

We study the problem of searching for a vertex with a desired property in the arrangement of a set of lines in the plane. We show that this problem can be solved efficiently by modifying (and simplifying) two slope selection algorithms without using parametric search. We apply this result to a points approximation problem and obtain an optimal solution for it without using parametric search. Since this line arrangement searching problem is quite natural, our result may find other applications as well.     

Approximation algorithms for partitioning a rectangle with interior points

LetR be a rectangle and letP be a set of points located insideR. Our problem consists of introducing a set of line segments of least total length to partition the interior ofR into rectangles. Each rectangle in a valid partition must not contain points fromP as interior points. Since this partitioning problem is computationally intractable (NP-hard), we present efficient approximation algorithms for its solution. The solutions generated by our algorithms are guaranteed to be within three times the optimal solution value. Our algorithm also generates solutions within four times the optimal solution value whenR is a rectilinear polygon. Our algorithm can be generalized to generate good approximation solutions for the case whenR is a rectilinear polygon, there are rectilinear polygonal holes, and the sum of the length of the boundaries is not more than the sum of the length of the edges in an optimal solution.A preliminary version of this paper appeared in theProceedings of the Symposium on Computational Geometry, June 1985, pp. 281–287. This research was supported in part by the National Science Foundation under Grant DCR-8503163.     

主子阵约束下矩阵方程AX=B的对称最小二乘解

本文主要讨论主子阵约束下矩阵方程AX=B的对称最小二乘解．基于投影定理,巧妙的把最小二乘问题转化为等式问题求解,并利用奇异值分解的方法,给出了该对称最小二乘解的一般表达式．此外,文章还考虑了此对称最小二乘解集合对任一给定矩阵的最佳逼近问题,得到了最佳逼近解,并给出了相应的算法步骤和数值例子．     

Translational Covering of Closed Planar Cubic B-Spline Curves

Spline curves are useful in a variety of geometric modeling and graphics applications and covering problems abound in practical settings. This work defines a class of covering decision problems for shapes bounded by spline curves. As a first step in addressing these problems, this paper treats translational spline covering for planar, uniform, cubic B‐splines. Inner and outer polygonal approximations to the spline regions are generated using enclosures that are inside two different types of piecewise‐linear envelopes. Our recent polygonal covering technique is then applied to seek translations of the covering shapes that allow them to fully cover the target shape. A feasible solution to the polygonal instance provides a feasible solution to the spline instance. We use our recent proof that 2D translational polygonal covering is NP‐hard to establish NP‐hardness of our planar translational spline covering problem. Our polygonal approximation strategy creates approximations that are tight, yet the number of vertices is only a linear function of the number of control points. Using recent results on B‐spline curve envelopes, we bound the distance from the spline curve to its approximation. We balance the two competing objectives of tightness vs. number of points in the approximation, which is crucial given the NP‐hardness of the spline problem. Examples of the results of our spline covering work are provided for instances containing as many as six covering shapes, including both convex and nonconvex regions. Our implementation uses the LEDA and CGAL C++ libraries of geometric data structures and algorithms.     

An Improved Parameterized Controller Reduction Technique via New Frequency Weighted Model Reduction Formulation

In this paper, an improved parameterized controller reduction technique via a new frequency weighted model reduction formulation is developed for the feedback control of MIMO discrete time systems particularly for non‐unity feedback control system configurations which have the controller located in the feedback path. New frequency weights which are a function of a free parameter matrix are derived based on a set of equivalent block diagrams and this leads to a generalized double sided frequency weighted model reduction formulation. Solving this generalized double sided frequency weighted model reduction problem for various values of the free parameter results in obtaining controllers which correspond to each value of the free parameter. It is shown that the proposed formulation has a useful characteristic such that selecting a controller which corresponds to a large value of the free parameter results in obtaining an optimal reduced order controller and using this optimal reduced order controller in a closed loop system results in significant reduction in the infinity norm of the approximation error between the original closed loop system and the closed loop system which uses an optimal reduced order controller (when compared to existing frequency weighted model reduction methods).     

Reconstruction of polycrystalline structures: a new application of combinatorial optimization

Many known materials possess polycrystalline structure. The images produced by plane cuts through such structures are polygonal complexes. The problem of finding the edges, when only the vertices of a given polygonal complex are known, is considered. A combinatorial optimization model is proposed whose solution yields an approximation of the complex. The problem itself is solved using simulated annealing. Encouraging first experiments are presented.     

A mesh optimization algorithm based on neural networks

We have developed a mesh simplification method called GNG3D which is able to produce high quality approximations of polygonal models. This method consists of two distinct phases: an optimization phase and a reconstruction phase. The optimization phase is developed by applying an extension algorithm of the growing neural gas model, which constitutes an unsupervised incremental clustering algorithm. The primary goal of this phase is to obtain a simplified set of vertices representing the best approximation of the original 3D object. In the reconstruction phase we use the information provided by the optimization algorithm to reconstruct the faces obtaining the optimized mesh as a result. We study the model theoretically, analyzing its main components, and experimentally, using for this purpose some 3D objects with different topologies. To evaluate the quality of approximations produced by the method proposed in this paper, three existing error measurements are used. The ability of the model to establish the number of vertices of the final simplified mesh is demonstrated in the examples.