Verification of Properties of Geometric Structures and Reconstruction of Geometric Objectsfrom Partial Information

DMS-0310589凯伦丹尼尔斯，丹尼尔克莱恩，库斯坦廷雷布尼科夫这是一个货物孵化奖下征求http://www.nsf.gov/pubs/2002/nsf02155/nsf02155.htm.The调查人员将开发新的技术和算法，解决一系列问题，解决验证和重建几何对象的部分信息。 该方法分为两个阶段：首先，验证部分信息是否与预期结果一致。第二，如果答案是肯定的，重建对象。 如果答案是否定的，则找到所需重建的近似值。 该小组将集中讨论四类主要问题。 第一类是一般的NP-难包容、覆盖和填充问题。 虽然关于对象的完整信息可能是可用的，但由于问题的难度，将使用部分信息。 除了加强现有的多边形形状的算法，这项工作将设计的第一个包含和覆盖算法使用对象的样条曲线。对于其他三个问题，只有部分信息的对象是可用的。 第二个问题是凸多面体和凸光滑形状的凸性验证和重构。 从部分数据重建凸多面体是一个迷人的经典问题，可以追溯到麦克斯韦，斯坦尼茨和闵可夫斯基。虽然已经做了大量的工作，从投影的凸多面体的识别和重建，重建光滑的凸形状与一个给定的离散参数集是一个问题，尚未得到充分解决。我们的工作将着重于用样条重构凸光滑体。 第三个问题是从有限的样本点集统计确定物体的拓扑性质，如欧拉特征线。 第四个问题与第三个问题密切相关，它是由非凸体在有限个平面上的投影确定非凸体的拓扑。 在第三和第四个问题中，对估值的剖析和随后的使用，即可加性概率测度，将发挥特别重要的作用。 数学和计算机科学研究人员团队将结合联合收割机计算几何技术，数学编程方法，图论和离散几何方法，凸性理论方法，以及多变量样条设计验证和重建算法。除了它们在纯数学和理论计算机科学中的意义外，这些问题对计算几何和几何软件设计的应用也很重要。例如，几何软件输出的度量和拓扑性质的验证对于实现和测试几何算法是重要的。 包容算法在用于制造的2D包装和布局中是有用的。 3D形状的包容性适用于建模任务，如分子对接和医疗计划。覆盖问题出现在实际环境中，如军事传感器覆盖和定位，电信，空间查询优化和图形。涉及样条的工作适用于计算机辅助设计和数值方法的设计。 从有限采样、投影和截面确定物体的拓扑结构是计算机层析成像和模式识别中的一个重要难题。

DMS-0310589Karen Daniels, Daniel Klain, Koonstantin RybnikovThis is a CARGO incubation award made under solicitation http://www.nsf.gov/pubs/2002/nsf02155/nsf02155.htm.The investigators will develop new techniques and algorithms for solving a collection of problems that address the verification and reconstruction of geometric objects from partial information. The approach is to have two stages: first, verify if the partial information is consistent with the desired outcome. Second, if the answer is positive, reconstruct the object. If the answer is negative, find an approximation to the desired reconstruction. The group will focus on four major types of problems. The first type is a general class of NP-hard containment, covering and packing problems. Although complete information about the objects may be available, partial information will be used due to the hardness of the problems. In addition to strengthening existing algorithms for polygonal shapes, this work will design the first containment and covering algorithms using objects bounded by spline curves. For the other three problems only partial information about the objects is available. The second problem is the verification of convexity and reconstruction of convex polyhedra and convex smooth shapes from partial data. Reconstruction of convex polytopes from partial data is a fascinating classical problem going back to Maxwell, Steinitz, and Minkowski. While much work has been done on recognition and reconstruction of convex polyhedra from projections, reconstruction of smooth convex shapes with a given discrete set of parameters is a problem that has not been adequately addressed. Our work will emphasize reconstruction of convex smooth bodies using splines. The third problem is that of statistical determination of topological properties of a body, such as the Euler characteristic, from a finite set of sample points. The fourth problem, tightly related to the third one, is the determination of the topology of a non-convex body from its projections on a finite number of planes. Dissection and subsequent use of valuations, i.e. finitely additive probability measures, will play an especially important role in the third and fourth problems. The team of mathematics and computer science investigators will combine computational geometry techniques, mathematical programming approaches, methods of graph theory and discrete geometry, methods of convexity theory, and work on multivariate splines to design verification and reconstruction algorithms. In addition to their significance in the context of pure mathematics and theoretical computer science, these problems are important to applications of computational geometry and geometric software design. For example, verification of metric and topological properties of geometric software outputs is important for implementing and testing geometric algorithms. Containment algorithms are useful in 2D packing and layout for manufacturing. Containment for 3D shapes is applicable to modeling tasks such as molecular docking and to medical treatment planning. Covering problems arise in practical settings such as military sensor coverage and targeting, telecommunications, spatial query optimization, and graphics. Work involving splines is applicable to CAD and design of numerical methods. Determination of the topology of a body from finite samplings, projections, and sections is a hard problem important for computer tomography and pattern recognition.