It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out...It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out that it would be interesting to compute the competition numbers of some triangulations of a sphere as he got the exact value of the competition numbers of regular polyhedra. In this paper, we study the competition numbers of several kinds of triangulations of a sphere, and get the exact values of the competition numbers of a 24-hedron obtained from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face, a class of dodecahedra constructed from a hexahedron by adding a diagonal in each face of the hexahedron, and a triangulation of a sphere with 3n (n≥2) vertices.展开更多
In this paper, we are addressing the exact the Voronoi diagram of spheres using Wu's algorithm. computation of the Delaunay graph (or quasi-triangulation) and Our main contributions are first a methodology for auto...In this paper, we are addressing the exact the Voronoi diagram of spheres using Wu's algorithm. computation of the Delaunay graph (or quasi-triangulation) and Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu's algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu's algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.展开更多
文摘It is hard to compute the competition number for a graph in general and characterizing a graph by its competition number has been one of important research problems in the study of competition graphs. Sano pointed out that it would be interesting to compute the competition numbers of some triangulations of a sphere as he got the exact value of the competition numbers of regular polyhedra. In this paper, we study the competition numbers of several kinds of triangulations of a sphere, and get the exact values of the competition numbers of a 24-hedron obtained from a hexahedron by adding a vertex in each face of the hexahedron and joining the vertex added in a face with the four vertices of the face, a class of dodecahedra constructed from a hexahedron by adding a diagonal in each face of the hexahedron, and a triangulation of a sphere with 3n (n≥2) vertices.
文摘In this paper, we are addressing the exact the Voronoi diagram of spheres using Wu's algorithm. computation of the Delaunay graph (or quasi-triangulation) and Our main contributions are first a methodology for automated derivation of invariants of the Delaunay empty circumsphere predicate for spheres and the Voronoi vertex of four spheres, then the application of this methodology to get all geometrical invariants that intervene in this problem and the exact computation of the Delaunay graph and the Voronoi diagram of spheres. To the best of our knowledge, there does not exist a comprehensive treatment of the exact computation with geometrical invariants of the Delaunay graph and the Voronoi diagram of spheres. Starting from the system of equations defining the zero-dimensional algebraic set of the problem, we are applying Wu's algorithm to transform the initial system into an equivalent Wu characteristic (triangular) set. In the corresponding system of algebraic equations, in each polynomial (except the first one), the variable with higher order from the preceding polynomial has been eliminated (by pseudo-remainder computations) and the last polynomial we obtain is a polynomial of a single variable. By regrouping all the formal coefficients for each monomial in each polynomial, we get polynomials that are invariants for the given problem. We rewrite the original system by replacing the invariant polynomials by new formal coefficients. We repeat the process until all the algebraic relationships (syzygies) between the invariants have been found by applying Wu's algorithm on the invariants. Finally, we present an incremental algorithm for the construction of Voronoi diagrams and Delaunay graphs of spheres in 3D and its application to Geodesy.