Polyhedral Approximation and Other Computational Aspects of Geometric Problems

研究者和他的同事从两个方向研究了各种几何问题的计算方面：(1)设计和实现了用多面体在多维空间中逼近各种凸和非凸物体的有效算法，并研究了这些算法的计算复杂性和实际效率。(2)应用高性能计算作为工具来解决或推进凸几何中开放理论问题的解决，其中包括Kneser问题，该问题涉及多维欧几里德空间中球的交点或并集的体积与其相互距离之间的关系。由于在许多应用领域中具有重要的实际意义，本文特别注意用“更简单”的多面体逼近凸多面体和非凸多面体，并给出了这些情况下的完全构造解。扩展和变体，如在各种度量下的近似，要求近似对象包围或包含在近似对象中，以及寻找特定类型的最小封闭多面体（例如平行四边形），也被考虑在内。其中一些变体在移动计算和多维数据库中得到了重要的应用。研究人员开发了有效的计算解决方案，以近似多面体（由平面形成的固体）的规定尺寸的多维体的问题。这种近似是许多学科的重要工具，包括分子建模、最优控制、计算机辅助设计和计算机可视化。他们还研究了用规定类型的多面体包围和逼近多维体的问题，例如“盒子”（平行四边形）。这些问题的解决方案在快速发展的移动计算和多维数据库领域得到了重要的应用。此外，由于它们的简单性，多面体是迄今为止使用最广泛的模型表示形式。因此，这项工作也很重要，因为它促进了对多面体已有的大量方法的使用，只要得到的近似是好的，并且可以有效地执行。这些算法的发展产生了高性能计算工具。研究者们依次使用这些工具来研究长期存在的几何问题。

The investigator and his colleague study computationalaspects of various geometric problems in two directions: (1)Design and implementation of efficient algorithms for theapproximation of various convex and nonconvex objects inmultidimensional space by polytopes, and research of thecomputational complexity as well as practical efficiency of thesealgorithms. (2) Application of high performance computing as atool to solve or advance toward a solution of open theoreticalproblems in convex geometry, among them, Kneser's problemconcerning the relationship between volumes of intersections orunions of balls in multidimensional Euclidean space and theirmutual distances. Because of its practical importance in manyapplication areas, the approximation of both convex and nonconvexpolytopes by "simpler" polytopes is given special attention, andfully constructive solutions are developed for these cases.Extensions and variants such as approximation under variousmetrics, requiring the approximating object to enclose or becontained within the approximated object, and finding minimalenclosing polytopes of a specific type (like parallelotopes, forexample), are also considered. Some of these variants findimportant applications in mobile computing and multidimensionaldatabases. The investigators develop efficient computational solutionsfor the problem of approximating multidimensional bodies bypolytopes (solids formed by flat faces) of a prescribed size.Such approximation is an important tool in many disciplines,including molecular modeling, optimal control, computer-aideddesign, and computer visualization. They also investigate theproblem of enclosing and approximating multidimensional bodies bypolytopes of a prescribed type, such as "boxes" (parallelotopes),for example. Solutions to these problems find importantapplications in the rapidly growing areas of mobile computing andmultidimensional databases. Furthermore, due to their simplicity,polytopes are by far the most widely used form of modelrepresentation. Thus, the work is also important because itfacilitates the use of the large body of methods alreadyavailable for polytopes, provided that the resultingapproximation is good and can be performed efficiently.Development of these algorithms produces tools of highperformance computing. The investigators use these tools in turnto study long-standing geometric problems.