关键词: 凹多面体, 凸剖分, 成功回路

Abstract: A new algorithm about decomposing an arbitrary non-convex polyhedron is proposed to convex polyhedrons without adding new vertexes.Firstly，the non-convex polyhedron is abstracted to undirected graph，the vertex of polyhedron for the vertices of graph，the edge and the diagonal edge of polyhedron for the edge of graph，the length of the edge or diagonal edge for the right value of graph.A successful loop is selected according to the minimum cost spanning tree that made by Prim algorithm.Then the non-convex is decomposed by using the successful loop.Repeat the processes until the polyhedral are convex.The algorithm can decompose the polyhedron without adding new vertexes.At the same time，it can decompose arbitrary non-convex polyhedrons that consist of holes.

Key words: non-convex polyhedron, convex decomposition, successful loop