Construction of Plat-form Models for the Problemof Packing Geometrical Objects

在本研究中，我们提出了“多球方案”，以有效地包装给定的二维或三维物体在一个紧凑的空间，设计了该方案的所有组件，并研究了几何包装和图形绘制的基本理论。在图论分析的基础上，设计了一种将给定的三角网格数据直接转换为多球格式数据的算法。我们开发了一个多球格式的三维可视化界面，通过它我们可以很容易地检查计算结果以可视化的形式。我们极大地改进了我们的求解器，以便我们的新求解器首次解决长期存在的开放基准实例。在理论部分，我们得到了三连通图的二维表示，从而可以方便地得到有用的三连通分解，并得到了一类非凸多面体图的特征，特别是后一个结果是自Steinitz定理以来的第一个结果，该定理是凸多面体图的特征。

In this study, we proposed "Multi-sphere Scheme" to efficiently pack given two- or three-dimensional objects in a compact space, designed all the components of the scheme, and investigated fundamental theory on geometrical packings and graph drawings. We designed an algorithm that can directly transform given triangle-mesh data into data for Multi-sphere Scheme based on a graph-theoretical analysis. We developed a 3D visual interface for Multi-sphere Scheme, by which we can easily check computational results in a visualized form. We greatly improved our solver for packing rectangles so that a long-standing open benchmark instance is solved for the first time by our new solver. As for the theory part, we found a 2D representation of triconnected graphs so that a useful triconnected decomposition can be easily obtained, and a characterization of the graphs of non-convex polytopes in a certain class.In particular, the latter result is the first such result since Steinitz' theorem, a characterization of the graphs of convex polytopes is found 80 years ago.