Computational Studies in Polyhedral Convexity: Lattice Points and Triangulations

多面体凸性的计算研究：格点和三角剖分

• 批准号: 0073815
• 负责人: Jesus De Loera
• 金额: $ 7.39万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2000
• 资助国家: 美国
• 起止时间: 2000-08-01 至 2003-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0073815&HistoricalAwards=false
• 关键词: Computational; Studies; Polyhedral; Convexity; Lattice

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.

de loera0073815研究者研究了凸多属性的最佳细分，覆盖物和三角剖分的组合和代数特性。 他开发了用于计算此类最佳对象的算法。 探索的最优标准包括最小化简单数量，简单总和或区域的总和以及简单的平均体积的最小化。 他还开发了用于计算低维多色内部和计算整数船体内所有晶格点的软件。 该技术还允许快速计算体积。 考虑特定的问题来评估软件的效率，例如在固定半径范围内的N点的最佳布置，从而最大程度地增加了其凸壳内的晶格点的数量。 由于Barvinok，该软件的算法是新技术的改编，这些新技术基于用单型简单覆盖Polyhedra。 该项目还包括来自凸，组合，整数和线性编程，交换代数，复杂性和强化计算机实验的方法。 这项工作的结果应该在整数编程，组合和符号 - 代数计算中引起人们的关注。 从非正式的角度来看，可以将该项目的第一部分视为试图理解如何有效地将对象（例如立方体和多边形）分解为基本块或零件。 这也许让人想起创造拼图游戏。 分解中使用的块是四面体，三角形或较小的立方体。 有效分解的一个例子是使用最少数量的碎片。 该项目的第二部分涉及建立实用的计算机软件，以计算常规边界内的定期分布点。 定期分布点的示例是原子或晶体的排列。 研究中的许多理论问题都是由计算机图形和计算机可视化问题（通过用于建模图的经济网格设计），数据安全和计算（在RSA加密的背景下，在Internet交易中使用的）和操作研究（通过某些技术来解决无确定性时解决Integer程序）的动机。 对学生的培训是该项目的重要组成部分。