Computational Studies in Polyhedral Convexity: Lattice Points and Triangulations

University Of California-Davis, Davis CA

Investigators

Abstract

De Loera 0073815 The investigator studies the combinatorial and algebraic properties of optimal subdivisions, coverings, and triangulations of convex polytopes. He develops algorithms for the computation of such optimal objects. Criteria of optimality that are explored include minimization of the number of simplices, of the total sum of lengths or areas of simplices, and of the average volume of the simplices. He also develops software for counting all lattice points inside a low-dimensional polytope and for computing their integer hulls. The technique also allows the fast computation of volumes. Specific problems are considered to assess efficiency of the software, for example the optimal arrangements of n points, in a sphere of fixed radius, that maximize the number of lattice points inside their convex hull. Algorithms for the software are adaptations of new techniques, due to Barvinok, that are based on covering polyhedra with unimodular simplices. This project also includes methods from convexity, combinatorics, integer and linear programming, commutative algebra, complexity, and intensive computer experimentation. The results of this work should be of interest in integer programming, combinatorics, and symbolic-algebraic computing. Informally speaking, the first part of this project can be thought of as an attempt to understand how to break or decompose objects, such as cubes and polygons, into elementary blocks or pieces efficiently. This is perhaps reminiscent of creating jigsaw puzzles. The blocks used in the decomposition are, for instance, tetrahedra, triangles, or smaller cubes. An example of efficient decomposition is to use the smallest number of pieces. The second part of the project involves establishing practical computer software for counting regularly distributed points within regular boundaries. Examples of regularly distributed points are arrangements of atoms or crystals. Many of the theoretical questions under study are motivated by problems in computer graphics and computer visualization (via the design of economic meshes for modeling figures), data security and computation (in the context of RSA encryption, which is used in internet transactions), and operations research (via certain techniques for solving integer programs when levels of uncertainty are expected). The training of students is an important component of the project.