多边形填充问题是指给定一个长宽已知的矩形容器和若干个边数、形状和大小已知的多边形，问能否将这些多边形互不相交地放入矩形容器。若能放入，则给出各个多边形在矩形容器中的放置方位，否则回答不能放入。　　多边形填充问题在平面布局、皮革和制衣工业中有广泛的应用价值，许多实际的布局问题、覆盖问题和裁剪问题都可最终归结为多边形填充问题的求解。同时它又是计算理论中的重要问题，例如在算法设计和复杂性分析中占有重要地位。理论和实践的需要使该问题的算法设计变得十分迫切，但由于它具有NP难度，因此其实用快速算法常常是近似的，多数学者在处理该问题时对其进行简化，例如不允许多边形旋转或者仅允许多边形取有限的几个放置方向，这种处理方式有其应用意义，并且如此简化后的问题是NP完全的，称之为平移多边形填充问题。　　为了给多边形填充问题设计一个有效的近似算法，撇开具体的应用背景，从理论分析的角度，提出了零自由度动作的概念，将多边形填充问题简化为一个NP完全的组合优化问题，并采取将多边形逐个地放入矩形容器的策略。在如何选择放置动作的问题上，提出了最小损伤的思想，并在此基础上设计出了一个快速近似算法——最小损伤法，复杂性分析证明了该算法为多项式时间算法，大量的实验数据也表明最小损伤法是非常有效的。为改善算法的完整度，提出了相应的回溯算法，实验表明回溯算法可大大改善解的质量，并且计算速度也没有显著降低，具有很强的实用性。尽管零自由度动作模型对原始问题有损，即在此模型下最优解可能被忽略，但它有物理学方面的依据，直观上，一个零自由度动作可以有效地利用空间。　　提出了一个精确求解多边形填充问题的代数方法。由于多边形填充问题是一个连续问题，在计算过程中必然要涉及到实数的运算，而精确处理实数是Turing机无能为力的，因此分析了实数的可计算性，指出了实数运算带来的误差性质及其影响。并且深入分析了多边形填充问题解格局的拓扑结构，证明了零自由度原理，即多边形填充问题有解当且仅当它存在紧缩解，将多边形填充问题的解空间从无穷变为有穷且对原问题无损，为精确求解奠定了基础。在此基础上，提出了精确求解多边形填充问题的代数方法，若忽略实数运算的误差，则求得的解是精确的。尽管实数的运算在理论上不可能达到完全精确，但如果有需要，仍然可以获得任意的计算精度。在该代数方法下，只需求解一个多项式方程组就可以获得多边形填充问题的精确解，该多项式方程组的大小为问题规模的多项式量级，并且其计算复杂性仅仅依赖于求解该多项式方程组的复杂性。对多项式方程组的计算复杂性没有展开讨论，这需要进一步研究。　　研究了两种类型的计算复杂性，即与有穷性有关的计算复杂性和与无穷性有关的计算复杂性，通过具体的例子指出了它们各自的特点。在此基础上，研究了与多边形填充问题有关的一些基础问题。如证明了多边形填充问题的一个特例——矩形的三角形划分问题是NP完全的，同时给出了该问题存在解的一个必要非充分条件;以三角形填充问题为例，找到了两种全局无损的放置动作并证明了其正确性，该结果对设计快速近似算法具有启发意义;根据解格局拓扑结构的不同特点，给填充问题类进行了复杂性分层，其意义在于给近似算法的设计提供理论分析依据。