Computational Studies in Polyhedral Convexity: Lattice Points and Triangulations

研究者研究了凸多面体的最优细分、覆盖和三角剖分的组合和代数性质。他开发了计算这类最优目标的算法。所探索的最优性标准包括简化的数量最小化，简化的长度或面积的总和最小化，以及简化的平均体积最小化。他还开发了用于计算低维多面体内所有点阵点和计算其整数壳的软件。该技术还允许快速计算体积。具体的问题被考虑来评估软件的效率，例如n个点的最优安排，在一个固定半径的球，使其凸包内的点阵点的数量最大化。该软件的算法是Barvinok提出的新技术的改编，该技术基于用非模简单体覆盖多面体。这个项目也包括了从凸性、组合学、整数和线性规划、交换代数、复杂性和密集的计算机实验的方法。这项工作的结果应该对整数规划、组合学和符号代数计算感兴趣。非正式地说，这个项目的第一部分可以被认为是试图理解如何有效地将物体（如立方体和多边形）分解为基本块或块。这可能让人想起制作拼图游戏。例如，分解中使用的块是四面体、三角形或更小的立方体。高效分解的一个例子是使用最小数量的碎片。该项目的第二部分涉及建立实用的计算机软件，用于计算规则边界内规则分布的点。规则分布点的例子是原子或晶体的排列。许多正在研究的理论问题都是由计算机图形学和计算机可视化（通过设计经济网格来建模数字）、数据安全和计算（在RSA加密的背景下，用于互联网交易）和运筹学（通过某些技术来解决整数程序，当预期的不确定性水平时）中的问题所激发的。对学生的培训是该项目的重要组成部分。

De Loera0073815 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.