Polyhedral Approximation and Other Computational Aspects of Geometric Problems

多面体逼近和几何问题的其他计算方面

• 批准号: 0107628
• 负责人: Mario Lopez
• 金额: $ 15.8万
• 依托单位: University of Denver
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-09-01 至 2006-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0107628&HistoricalAwards=false
• 关键词: Polyhedral; Approximation; Other; Computational; Aspects

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.

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