相似三角形的最优填充

托马斯J.理查森

我们证明了总面积等于alpha;的任何一组相似三角形都可以在面积为2alpha;的相似三角形内被打包，只需要平移和反射。边界2alpha;一般不能改进。这种证明是建设性的，给出了产生这种包装的快速算法。我们猜想，这样一个集合可以仅使用平移被打包在区域2alpha;的类似三角形内。

1介绍

二维装箱是一个非常重要的问题并行处理调度中的应用程序视图。有很少有最坏的情况能解决这个问题。对于概率结果，Coffman和Lueker[1]提供了几个例子和参考。Kleitman和Krieger[3]表明，单位总数的任何平方族区域可以被包装在一个大小为的矩形内，而不是面积较小的矩形可以满足这种包装性能。在[6]中，月球莫瑟表明，这样的方块可以被包装成一个正方形。其中h₁是要包装的最大正方形的尺寸。Meir和Moser[5]将[6]的结果推广到更高的维度。一般的最优包装问题是难以解决的，即：NP-hard [2]。

从纯几何的角度来看，考虑正方形和矩形以外的形状。在本文中，我们研究包装形状相同的三角形中的相似三角形。在最近的一篇论文中，Kranakis和Meertens[4]提出了一种简单而优雅的这个问题。他们声称这样生产的包装在一定意义（下面的保证定理1）和对于包装问题，三角包装具有一个简单而优雅的最优解决方案的罕见特性。事实上，这个问题提供了包装难题的另一个例证：他们的主张是不正确，如第2节所示，最佳填料似乎需要复杂的结构。在这里我们提供这样一种结构Kranakis-Meertens算法仍然发挥着作用。

让T表示欧几里得平面上的三角形。我们考虑打包给定集合的问题命中：相似三角形的{h_iT:1le;ile;n}变成一个三角形uT，目标是最小化u。我们考虑三个根据包装中允许的自由度变化。最多的限制是只允许通过平移打包。（在这种情况下，所有三角形是一个平移和扩张的等价模。）一个中间版本。允许通过平移和思考进行包装。限制最小的包装允许任意欧几里得运动。

问题的中间版本，允许平移和反射，是为了确定最小常数，beta;，这样对于任何l₂个非负实数的序列，h ₁≧h ₂≧hellip;，存在和使得构成在类似三角形内填充的不重叠三角形大小满足

上述声明也可适用于一般问题。如果允许任意欧几里得运动，则将S _i解释为任意旋转。下限beta;ge;2在两种情况下都适用，因为面积相等的三角形就可以实现。以下是本文的主要结论。

定理1：允许平移和思考，我们可以打包任何相似三角形族，总面积alpha;在相似三角形内2alpha;没有任何给定的三角形相互重叠。

定理1的证明是有建设性的。基本的想法是要小心在集合中打包几个最大的三角形点击：{h_iT:1le;ile;n}和然后使用Kranakis-Meertens算法打包其余部分。我们找到了它有必要考虑前几个不同的包装三角形。

当只允许平移时，我们不知道最佳界限。然而，我们相信相同的包装密度是可以实现的。

猜想1：仅允许平移，任何类似三角形族总面积alpha;可以填充在面积为2alpha;的类似三角形内。

2、Kranakis--Meertens打包算法

由于仿射变换保留了相对区域，因此反射模转换，并保持子集的不连续性，我们在不丧失一般性的情况下，可以假定t是等腰直角三角形。此后，我们修正

图1：一种带有五个三角形和相应螺旋体的包装条

kranakis-meertens打包算法的基本思想是打包三角形按大小顺序排列成条带。到开始，设置。设k为最大（奇数）整数（假设存在这样的k），并定义。对于每个定义;如果j是偶数集如果j是奇数集。设置T₂，T₃hellip;T_k-1构成不重叠梯形内填充三角形的配置。这种结构称为填料。与序列h₂，h₃，hellip;，h_k-1相关的条带。如果k＝7，则A生产如图1所示的密封条。随之而来的是T_1,hellip;,T_k-1用（包装。包装继续进行。递归：将上面给出的算法应用于序列(h₁ h₂),h_{2k 1},_,h_{2k 2},hellip;当所有三角形拥挤的。图2说明了这样构造的包装的形式

图2 算法生成的三角形的填充

对于三角形的任何填充，我们指的是填充三角形到其所在三角形的面积按包装密度包装。

反例。Kranakis -Meertens打包算法没有务必找到密度为1/2的填料。考虑下面的五个三角形例：h ₁=h₂=1，h₃=h₄=h₅=0.6。五个三角形alpha;的总面积为1.54。该算法将这些三角形打包成度为2.6的一个，面积3.38，大于2alpha;。

1. 定理1的证明

定理1的证明依赖于以下事实：只要给算法一个足够好的开始，它就可以工作。如果最大三角形可以被压缩得足够紧，然后算法可以把剩下的打包好。证据是逐案进行的，取决于最大三角形的相对大小。

我们会说序列h₁，h₂，hellip;具有TP（两个可打包）属性如果满足定理1的包装存在。为了简化符号，我们定义，并使用S表示

引理1:假设存在一个非重叠的三角形结构，T₁，hellip;，T _k-1（其中T _i=x_i s_ih_iT），封装在三角形内h₀T，h₀满足2h₀gt;5h_k，S_kgt;A(h₀ h_k)。如果我们应用Kranakis- Meertens包装算法到序列h₀，h_k，h_{k 1}，hellip;和打包T _1,hellip;,T_k-1通过适当的转换，则所得填料的密度大于或等于1/2；即TP属性保留。

证明。将kranakis-meertens包装算法应用于序列h₀,h_k,h_{k l}hellip;..设m_n为三角形的索引开始第n条；因此，m₁=0，m₂=k等。定义。为了三角形T₁hellip;hellip;，T_p被包装成三角形高度H_n。这些p三角形的填充密度总是大于第一个m_n三角形的填充密度。它是因此，足以证明前m的填料密度，三角形大于或等于所有n的1/2。证明如下：归纳。假设n=2为真。假设索赔是对某些人来说是正确的。如果包装算法在第n条上终止那么，引理是正确的，琐碎的。因此，我们假设至少n 1需要条带。定义，即第n条带上边缘的长度。第（n 1）条带启动只有当第n条带完成后，（n 1）条带中的最大三角形不大于第n条带中的最小三角形；因此，和。把这些不平等结合起来就可以得到

“条件”的lemma提供，由于我们获得。这些不等式意味着以下关系：

归纳假设，当与上式结合，

在需要有限多条的情况下，对证据进行总结。无限多的条带很容易通过限制来处理。

包装定理的大部分剩余证明都是针对表明这个引理的条件可以满足；即，我们包装最大的三角形试图达到足够密集的填充，以便Kranakis-Meertens打包算法可以接管。结果是有几个案例需要考虑。证据通过消除。

引理2:如果h₃ h₅le;h₁，则TP属性保持不变。

证明：这里的想法基本上是将打包算法应用于重新排序的序列h₂，h₁，h₃，h₄hellip;.除了两条从T₁扩展而不是只扩展一个。

假设它存在，让p是最小的奇数，这样h₃ h₅ hellip; h_pgt;h₂，假设它存在，那么q是最小的奇数。整数，使h_p h_{p 2} ，hellip;， h_qgt;h₂。形成密封条与序列{h₁，h₃，hellip;，h_p-1}相关，也与序列{h₁，h_p，hellip;，h_q-1}相关对于用x _i替换x_i (h₃,-h₃)。所得配置与h₂T一起，是T₁，hellip;，T_q-1的非重叠配置，打包成(0.-h_i) (h₁ h₂)T图3说明了当p=5和q=7时的想法。如果p或q如果不存在，则包装已完成，且TP属性保持不变。从S₂ge;A(h₁ h₂)开始。如果存在q，则使用T_q启动第三条带。

图3 引理2包装三角形

由于h₃ h₅ hellip; h_pgt;h₂和qge;p 2，我们有

这意味着下面的第二个不等式：

此外，总部h_ple;h₅le;1/2h，3h_q le;h₁ h₂，和条件满足引理1

引理3。如果5h₅＞2(h₁ h₂)物业持有的话，TP属性保持。

证明，让m_n表示以第n条开始的三角形的索引根据Kranakis Meertens的打包算法，让。假设5h₅gt;2(h₁ h₂)，我们得到3h₅gt;2h₁，这意味着m₃＝5。现在，

因此，如果不需要第四个条带，则TP属性保持不变。假设，现在，需要第四条并定义

打包算法确保w h_m4gt;h₁ h₂。

图4 引理3包装三角形

我们考虑两个案例。第一个需要。在此之下假设Kranakis-Meertens算法成功。我们有。加上假设，这证实了

将其与等式（1）结合，得出

由于3h_m4le;h₁ h₂ h₅=H₃，我们得出以下条件：引理1现在满足于h₀=H₃和k=m₄。

对于第二种情况，我们有（这意味着m₄=10）。这里我们使用图4所示的包装。有两种情况根据h₂ h₄ h₅或h₁ h₂ h₇较大。如果第一个更大，我们按以下步骤进行

然后，由于3h₁₀ le;h ₂ h₄ h₅，引理1的条件是满足h₀=h ₂ h₄ h₅和K=10。当h₁ h₂ h₇较大时我们使用来推断，因此，

利用这个不等式，我们得到

引理1同样适用于h₀=h₁ h₂ h₇和k=10。这个完成了引理3的证明。

引理4。如果，则TP属性保持不变。

证明。同样，让m_n表示以根据Kranakis Meertens包装算法进行第n次剥离H_n表示它们的部分和。使用引理2和引理3，我们可以假设m₃=5，5h₅lt;2(h₁ h₂₎。在这些条件下，Kranakis Meertens算法有效。引理1的条件是如果我们证明，对h₀=h₁ h₂和k=5满意

现在

剩余内容已隐藏，支付完成后下载完整资料

英语原文共 13 页，剩余内容已隐藏，支付完成后下载完整资料

资料编号：[276524]，资料为PDF文档或Word文档，PDF文档可免费转换为Word