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.