Nowicki Tomasz, Tresser Charles
IBM, P.O. Box 218, Yorktown Heights, New York 10598, USA.
Chaos. 2004 Mar;14(1):55-71. doi: 10.1063/1.1624652.
A greedy algorithm for scheduling and digital printing with inputs in a convex polytope, and vertices of this polytope as successive outputs, has recently been proven to be bounded for any convex polytope in any dimension. This boundedness property follows readily from the existence of some invariant region for a dynamical system equivalent to the algorithm, which is what one proves. While the proof, and some constructions of invariant regions that can be made to depend on a single parameter, are reasonably simple for convex polygons in the plane, the proof of boundedness gets quite complicated in dimension three and above. We show here that such complexity is somehow justified by proving that the most natural generalization of the construction that works for polygons does not work in any dimension above two, even if we allow for as many parameters as there are faces. We first prove that some polytopes in dimension greater than two admit no invariant region to which they are combinatorially equivalent. We then modify these examples to get polytopes such that no invariant region can be obtained by pushing out the borders of the half spaces that intersect to form the polytope. We also show that another mechanism prevents some simplices (the simplest polytopes in any dimension) from admitting invariant regions to which they would be similar. By contrast in dimension two, one can always get an invariant region by pushing these borders far enough in some correlated way; for instance, pushing all borders by the same distance builds an invariant region for any polygon if the push is at a distance big enough for that polygon. To motivate the examples that we provide, we discuss briefly the bifurcations of polyhedra associated with pushing half spaces in parallel to themselves. In dimension three, the elementary codimension one bifurcation resembles the unfolding of the elementary degenerate singularity for codimension one foliations on surfaces. As the subject of this paper is new for the communities most interested in Chaos, we take some care in describing various links of our problem to classical issues (in particular linked to Diophantine approximation) as well as to various technological or commercial issues, exemplified, respectively, by digital printing and a problem in scheduling.
一种用于调度和数字印刷的贪婪算法，其输入为凸多面体，输出为该多面体的顶点序列，最近已被证明对于任意维度的任意凸多面体都是有界的。这种有界性属性很容易从与该算法等效的动力系统存在某个不变区域得出，这正是人们所证明的。虽然对于平面凸多边形，证明以及一些可以依赖单个参数构建的不变区域相当简单，但在三维及更高维度中，有界性的证明变得相当复杂。我们在此表明，这种复杂性在某种程度上是合理的，因为我们证明了适用于多边形的构造的最自然推广在二维以上的任何维度都不起作用，即使我们允许使用与面一样多的参数。我们首先证明，维度大于二的一些多面体不存在与它们组合等价的不变区域。然后我们修改这些例子以得到多面体，使得通过推出相交形成多面体的半空间的边界无法获得不变区域。我们还表明，另一种机制阻止了一些单纯形（任意维度中最简单的多面体）存在与其相似的不变区域。相比之下，在二维中，总是可以通过以某种相关方式将这些边界推得足够远来获得不变区域；例如，如果推动距离对于该多边形足够大，那么以相同距离推动所有边界可为任何多边形构建一个不变区域。为了说明我们提供的例子，我们简要讨论与平行于自身推动半空间相关的多面体的分岔。在三维中，基本的余维一分岔类似于曲面上余维一叶状结构的基本退化奇点的展开。由于本文的主题对于对混沌最感兴趣的群体来说是新的，我们在描述我们的问题与经典问题（特别是与丢番图逼近相关的问题）以及各种技术或商业问题的各种联系时非常谨慎，这些问题分别以数字印刷和调度问题为例。
