在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中, h, n 和s 分别是P的边界、边和凸顶点的数目...在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中, h, n 和s 分别是P的边界、边和凸顶点的数目; t 和r 分别是位于P的凸包上的顶点和边数同时。展开更多
Solving Algebraic Problems with Geometry Diagrams(APGDs)poses a significant challenge in artificial intelligence due to the complex and diverse geometric relations among geometric objects.Problems typically involve bo...Solving Algebraic Problems with Geometry Diagrams(APGDs)poses a significant challenge in artificial intelligence due to the complex and diverse geometric relations among geometric objects.Problems typically involve both textual descriptions and geometry diagrams,requiring a joint understanding of these modalities.Although considerable progress has been made in solving math word problems,research on solving APGDs still cannot discover implicit geometry knowledge for solving APGDs,which limits their ability to effectively solve problems.In this study,a systematic and modular three-phase scheme is proposed to design an algorithm for solving APGDs that involve textual and diagrammatic information.The three-phase scheme begins with the application of the statetransformer paradigm,modeling the problem-solving process and effectively representing the intermediate states and transformations during the process.Next,a generalized APGD-solving approach is introduced to effectively extract geometric knowledge from the problem’s textual descriptions and diagrams.Finally,a specific algorithm is designed focusing on diagram understanding,which utilizes the vectorized syntax-semantics model to extract basic geometric relations from the diagram.A method for generating derived relations,which are essential for solving APGDs,is also introduced.Experiments on real-world datasets,including geometry calculation problems and shaded area problems,demonstrate that the proposed diagram understanding method significantly improves problem-solving accuracy compared to methods relying solely on simple diagram parsing.展开更多
Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the min...Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.展开更多
文摘在对多边形P的外部Voronoi图的性质进行研究的基础上,将其表示成树结构并利用树结构的性质给出了其所含Voronoi顶点和边数的上界n+s+2×h-r-t-2和2×n+2×s+3×h-r-t-3,其中, h, n 和s 分别是P的边界、边和凸顶点的数目; t 和r 分别是位于P的凸包上的顶点和边数同时。
基金supported by the National Natural Science Foundation of China(No.61977029)the Fundamental Research Funds for the Central Universities,CCNU(No.3110120001).
文摘Solving Algebraic Problems with Geometry Diagrams(APGDs)poses a significant challenge in artificial intelligence due to the complex and diverse geometric relations among geometric objects.Problems typically involve both textual descriptions and geometry diagrams,requiring a joint understanding of these modalities.Although considerable progress has been made in solving math word problems,research on solving APGDs still cannot discover implicit geometry knowledge for solving APGDs,which limits their ability to effectively solve problems.In this study,a systematic and modular three-phase scheme is proposed to design an algorithm for solving APGDs that involve textual and diagrammatic information.The three-phase scheme begins with the application of the statetransformer paradigm,modeling the problem-solving process and effectively representing the intermediate states and transformations during the process.Next,a generalized APGD-solving approach is introduced to effectively extract geometric knowledge from the problem’s textual descriptions and diagrams.Finally,a specific algorithm is designed focusing on diagram understanding,which utilizes the vectorized syntax-semantics model to extract basic geometric relations from the diagram.A method for generating derived relations,which are essential for solving APGDs,is also introduced.Experiments on real-world datasets,including geometry calculation problems and shaded area problems,demonstrate that the proposed diagram understanding method significantly improves problem-solving accuracy compared to methods relying solely on simple diagram parsing.
基金Project supported by the National Nature Science Foundation of China (Nos. 60473103 and 60473127) and the Natural Science Foundation of Shandong Province (No. Y2005G03), China
文摘Computing the distance between two convex polygons is often a basic step to the algorithms of collision detection and path planning. Now, the lowest time complexity algorithm takes O(logm+logn) time to compute the minimum distance between two disjoint convex polygons P and Q, where n and m are the number of the polygons’ edges respectively. This paper discusses the location relations of outer Voronoi diagrams of two disjoint convex polygons P and Q, and presents a new O(logm+logn) algo- rithm to compute the minimum distance between P and Q. The algorithm is simple and easy to implement, and does not need any preprocessing and extra data structures.
