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.

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