Karen Daniels, Daniel Klain, Koonstantin Rybnikov
This is a CARGO incubation award made under solicitation 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.
