RIA: Network and Polyhedral Approximations

这个项目将研究几何对象的近似方案。考虑的几何对象是欧几里得网络和多面体。欧几里得网络在几何网络建模、电路互连等方面有着广泛的应用。多面体被用来模拟几乎任何真实的空间填充对象，例如机器部件、汽车和机器人。处理这些几何对象的算法的复杂性通常取决于对象本身的复杂性。要研究的近似方案将尝试用更简单的对象替换原始对象，使得原始对象的相关属性被更简单的对象保留。人们希望以后的计算能加快速度。对于稠密欧几里得网络，将以这样的方式消除边的子集，使得在较稀疏的网络中，任何一对顶点之间的通信路径不会明显地被延长。对于多面体，曲面将被包含更少平面部件的更简单的曲面所取代，但仍保留了重要的原始属性。

This project will investigate approximation schemes for geometric objects. The geometric objects considered are Euclidean Networks and Polyhedra. Euclidean networks have diverse applications, such as in modeling geometric networks and circuit interconnections. Polyhedra are used to model almost any real space filling object, such as machine parts, automobiles, and robots. The complexity of algorithms that manipulate these geometric objects often depends upon the complexity of the objects themselves. The approximation schemes to be studied will attempt to replace the original objects by simpler ones such that relevant properties of the original objects are retained by the simpler objects. The hope is, later computations get sped up. For dense Euclidean networks, a subset of the edges will be eliminated in such a manner that in the sparser network communication paths between any pair of vertices is not appreciably lengthened. For polyhedra, the surface will be replaced by a simpler one containing fewer planar pieces, yet retaining important original properties.