Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of p...Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-Destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-Destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computa- tional results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be con- veniently used for solving polygon packing problem.展开更多
In this article,we have given the definition of the Heilbronn number of n-noncollinear points in the plane. By this, we got the exact value of H5 which is the exact upper bound of H5 (K), where H5 (K) is any Heilbronn...In this article,we have given the definition of the Heilbronn number of n-noncollinear points in the plane. By this, we got the exact value of H5 which is the exact upper bound of H5 (K), where H5 (K) is any Heilbronn number in common sense.展开更多
With an error compensation term in the fractal Rayleigh quotient of PDE eigen-problems,we propose a new scheme by perturbing the mass matrix Mhto Mh=Mh+Ch2mKh,where Khis the corresponding stif matrix of a 2m 1 degree ...With an error compensation term in the fractal Rayleigh quotient of PDE eigen-problems,we propose a new scheme by perturbing the mass matrix Mhto Mh=Mh+Ch2mKh,where Khis the corresponding stif matrix of a 2m 1 degree conforming finite element with mesh size h for a 2m-order self-adjoint PDE,and the constant C exists in the priority error estimationλh jλj^Ch2mλ2j.In particular,for Laplace eigenproblems over regular domains in uniform mesh,e.g.,cube,equilateral triangle and regular hexagon,etc.,we find the constant C=I h 1Mh2 hKh and show that in this case the computation accuracy can raise two orders,i.e.,fromλh jλj=O(h2)to O(h4).Some numerical tests in 2-D and 3-D are given to verify the above arguments.展开更多
A three-node triangular element fitted to numerical manifold method with continuous nodal stress, called Trig_3-CNS(NMM)element, was recently proposed for linear elastic continuous problems and linear elastic simple c...A three-node triangular element fitted to numerical manifold method with continuous nodal stress, called Trig_3-CNS(NMM)element, was recently proposed for linear elastic continuous problems and linear elastic simple crack problems. The Trig_3-CNS(NMM) element can be considered as a development of both the Trig_3-CNS element and the numerical manifold method(NMM).Inheriting all the advantages of Trig_3-CNS element, calculations using Trig_3-CNS(NMM) element can obtain higher accuracy than Trig_3 element without extra degrees of freedom(DOFs) and yield continuous nodal stress without stress smoothing. Inheriting all the advantages of NMM, Trig_3-CNS(NMM) element can conveniently treat crack problems without deploying conforming mathematical mesh. In this paper,complex problems such as a crucifix crack and a star-shaped crack with many branches are studied to exhibit the advantageous features of the Trig_3-CNS(NMM) element. Numerical results show that the Trig_3-CNS(NMM) element is prominent in modeling complex crack problems.展开更多
文摘Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. Triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-Destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-Destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computa- tional results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be con- veniently used for solving polygon packing problem.
文摘In this article,we have given the definition of the Heilbronn number of n-noncollinear points in the plane. By this, we got the exact value of H5 which is the exact upper bound of H5 (K), where H5 (K) is any Heilbronn number in common sense.
基金supported by National Natural Science Foundation of China (Grant Nos.60970089,61170075 and 91230109)
文摘With an error compensation term in the fractal Rayleigh quotient of PDE eigen-problems,we propose a new scheme by perturbing the mass matrix Mhto Mh=Mh+Ch2mKh,where Khis the corresponding stif matrix of a 2m 1 degree conforming finite element with mesh size h for a 2m-order self-adjoint PDE,and the constant C exists in the priority error estimationλh jλj^Ch2mλ2j.In particular,for Laplace eigenproblems over regular domains in uniform mesh,e.g.,cube,equilateral triangle and regular hexagon,etc.,we find the constant C=I h 1Mh2 hKh and show that in this case the computation accuracy can raise two orders,i.e.,fromλh jλj=O(h2)to O(h4).Some numerical tests in 2-D and 3-D are given to verify the above arguments.
基金the National Natural Science Foundation of China(Grant Nos 51609240,11572009&51538001)and the National Basic Research Program of China(Grant No 2014CB047100)
文摘A three-node triangular element fitted to numerical manifold method with continuous nodal stress, called Trig_3-CNS(NMM)element, was recently proposed for linear elastic continuous problems and linear elastic simple crack problems. The Trig_3-CNS(NMM) element can be considered as a development of both the Trig_3-CNS element and the numerical manifold method(NMM).Inheriting all the advantages of Trig_3-CNS element, calculations using Trig_3-CNS(NMM) element can obtain higher accuracy than Trig_3 element without extra degrees of freedom(DOFs) and yield continuous nodal stress without stress smoothing. Inheriting all the advantages of NMM, Trig_3-CNS(NMM) element can conveniently treat crack problems without deploying conforming mathematical mesh. In this paper,complex problems such as a crucifix crack and a star-shaped crack with many branches are studied to exhibit the advantageous features of the Trig_3-CNS(NMM) element. Numerical results show that the Trig_3-CNS(NMM) element is prominent in modeling complex crack problems.
