Geometric Packing, Covering and Path Planning

将一组对象打包到一个有限的容器中以及由一组对象覆盖一些空间的问题是已知的困难(NP-完全)计算问题。这些问题的几何形式在计算机辅助制造中的下料和计算机视觉中的模板目标识别等领域有着广泛的应用。这项研究旨在通过考虑包装或覆盖的内部密度，即通过确定在无限空间中排列物体的最佳方式，而忽略边界，来寻求这些问题的易于处理但有趣的公式。在路径规划方面，将研究平面上一组障碍物的配置如何影响避开障碍物的最短路径的结构。该研究特别关注两点之间的最短路径是单调的，即它不相对于连接起点和目标点的线段反转方向。单调最短路径是令人感兴趣的，因为(1)如果已知最短路径是单调的，则可以有效地找到最短路径，以及(2)路径规划的许多应用涉及单调的最短路径查询。

The problems of packing a set of objects into a finite container and of covering some space by a set of objects are known to be hard (NP- complete) computational problems. Geometric versions of these problems have many applications in areas such a stock cutting in computer-aided manufacturing and object recognition by templates in computer vision. The research is directed towards tractable, yet interesting formulations of these problems by considering the internal density of the packing or covering, that is by determining the best way of arranging objects in an infinite space, ignoring boundaries. In the area of path planning it will be investigated how the configuration of a set of obstacles in the plane affects the structure of shortest paths that avoid the obstacles. The research is particularly concerned with the conditions under which the shortest path between two points is monotonic, that is, it does not reverse direction relative to the line segment joining its start and goal points. Monotonic shortest paths are of interest, because (1) shortest paths can be found efficiently if they are known to be monotonic, and (2) many applications of path planning involve shortest path queries that are monotonic.