Topics in Discrete Geometry: Packing and Covering

离散几何主题：堆积和覆盖

• 批准号: 9704319
• 负责人: Wlodzimierz Kuperberg
• 金额: $ 3.51万
• 依托单位: Auburn University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 1997
• 资助国家: 美国
• 起止时间: 1997-09-15 至 1999-10-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9704319&HistoricalAwards=false
• 关键词: Topics; Discrete; Geometry; Packing; Covering

The two investigators propose to continue their study of packing and covering of space with congruent replicas of a convex body, including the analytical and the combinatorial aspects of the topics. In their previous work, they obtained many results in dimension 2, and some in dimension 3 and higher. The proposed research concentrates on the covering problems in dimensions 3 and, whenever feasible, in higher dimensions. The common thread linking the various problems is the sphere covering conjecture in 3 dimensions. The following topics are the main subjects of the proposed investigation: covering space with parallel strings of spheres; covering space with congruent circular cylinders of infinite length; circle covering (of the plane) with a margin; stability properties of sphere coverings. The topics mentioned above belong to the area of discrete geometry, and some of them, especially those dealing with lattice arrangements, are related to the geometry of numbers. The problems addressed by the investigators have an intuitive flavor and a natural motivation. For instance, the sphere covering problem can be interpreted as searching for the most economical distribution of transmission stations whose ranges are spherical and of equal sizes to cover the whole space, i.e. so that every point is within reach of at least one of the stations. Whenever it is discovered that a certain optimality condition (e.g. minimum density, as in the example of transmission stations distribution) of an arrangement of figures or solids implies some regularity of the arrangement, a powerful tool is provided for computational geometry. Results of this type give a theoretical foundation for finding efficient computational algorithms. The investigators propose to increase their contributions to this important and difficult area of research.

这两位研究人员建议继续他们的研究包装和覆盖的空间与全等副本的凸体，包括分析和组合方面的主题。在他们以前的工作中，他们在二维中获得了许多结果，有些在三维和更高的维度中获得了一些结果。建议的研究集中在覆盖问题的尺寸3，并在可行的情况下，在更高的维度。连接各种问题的共同线索是三维空间中的球面覆盖猜想。以下主题是拟议的调查的主要课题：覆盖空间与平行字符串的领域;覆盖空间与全等圆柱体的无限长度;圆覆盖（平面）与保证金;稳定性性质的领域覆盖。 上面提到的主题属于离散几何领域，其中一些，特别是那些处理晶格排列的主题，与数字几何有关。调查人员所解决的问题有一种直观的味道和自然的动机。例如，球面覆盖问题可以被解释为寻找发射站的最经济分布，这些发射站的范围是球面的并且具有相等的大小以覆盖整个空间，即，使得每个点都在至少一个站的范围内。每当发现图形或实体的排列的某种最优性条件（例如，最小密度，如在发射站分布的例子中）意味着这种排列的某种规律性时，计算几何学就提供了一种强有力的工具。这种类型的结果为寻找有效的计算算法提供了理论基础。研究人员建议增加他们对这一重要而困难的研究领域的贡献。