Research On Optimization And Acceleration Algorithm In Digital Geometry Processing

As a new interdisciplinary,digital geometry processing does not only inherite a lot of traditional mathematics theories and methods,but also show its unique characteristics of the disciplined.In particular,the combination of numerical optimization theories and geometric methods provides a very practical and effective solution for the series of core problems in digital geometry processing and is successfully applied to several important occasions in geometric modeling and geometric processing.In this paper,the geometric iterative method in geometric modeling and the disk covering problem in geometric processing are used as breakthrough points.Based on the geometric properties of the problem itself and the classical numerical optimization theories,this paper explores a general situation in the field of digital geometric processing of the algorithm to accelerate the skills,and with a large number of numerical experiments to verify its practicality and effectiveness.(1)Considering that the traditional geometric iteration method has only the first-order convergence,we propose a second-order energy function to describe the difference between the current curve and the target point set.Firstly,the initial spline curve is generated according to the initial control points and the corresponding basis functions,and then the gradient of the difference function on each control vertex is obtained.Finally,the L-BFGS algorithm is used to find the optimal interpolation or approximation curve.The experimental results show that the algorithm has a super-linear convergence rate and tens or even hundreds of times faster than the original geometric iteration method at the same precision requirement.It can be used for both interpolation and approximation problems and also in the case where the parameter of data points are variable.(2)The covering and packing problems take a scientific challenge both in the theoretical and computational fields.Even if the optimized target zone is a plane in 2D space,the optimization problem of covering and packing problems are still a NP-complete problem.In this paper,we propose a new optimization algorithm to achieve covering and packing in a more general case,and the algorithm can be extended to non-Euclidean space(such as compact Riemannian manifold).The idea of this algorithm is based on the following two basic techniques: First,the disk covering problem(respectively,the disk packing problem)is closely related to the Voronoi diagram,that is,the local optimal solution of the covering problem(respectively,the disk packing problem)can be obtained by repeatedly updating the candidate center to the corresponding circumscribed(respectively,inscribed circle)of the corresponding Voronoi cells;the second point,the circumscribed circle(respectively,inscribed circle)can be approximated by the sample set ?-dense of the target region ?.The experimental results of this paper prove the feasibility and correctness of the algorithm.