Unique sink orientations of cubes
Unique sink orientations of cubes
复制标题
DOI：
10.1109/sfcs.2001.959931
复制
发表时间：
2001-10
期刊：
影响因子：
--
通讯作者：
Tibor Szabó;E. Welzl
中科院分区：
文献类型：
--
作者：
Tibor Szabó;E. Welzl
假设我们得到了一个 n 维超立方的边图，其边的方向使得每个面都有一个唯一的水槽。我们感兴趣的是在隐含给出方向的情况下，找到整个立方体的唯一水槽。基本操作是所谓的顶点评估，我们可以访问立方体的任意顶点，从而获得入射边的方向。当变形几何 n 维立方体（即具有立方体组合结构的多面体）的边缘根据某个通用线性函数定向时，就会出现唯一的汇定向。这些定向很容易被视为非循环的。研究唯一水槽定向的主要动机是某些线性互补问题，这些问题允许这种组合抽象（源自 Stickney 和 Watson，1978 年），在这些问题中会出现循环定向。同样，一些二次优化问题，如计算有限点集的最小包围球，也可以表述为在唯一水槽定向中寻找水槽（可能存在循环）。对于非循环的唯一水槽方向，人们已经知道伯恩德-加特纳（Bernd Gartner）（1998，2001）提出的随机程序，其预期顶点评估次数最多为 e/sup 2/spl radic/n/。对于一般情况，存在一个简单的随机 (3/2)/sup n/ 程序（文献中没有明确提及）。我们提出了新的算法，一个确定性的 O(1.61/sup n/) 程序和一个随机的 O((43/20)/sup n/2/)=O(1.47/sup n/)程序，用于唯一的汇方向。这些算法的一个有趣之处在于，它们并不沿着通往水槽的路径（类似于单纯形的方式）前进，而是利用了随机访问（在任意访问的意义上）立方体任意顶点的潜力。我们认为这一特点是本文的主要贡献。我们相信，独特的水槽方向具有丰富的结构，而且上述边界还有很大的改进空间。
Suppose we are given (the edge graph of) an n-dimensional hypercube with its edges oriented so that every face has a unique sink. Such an orientation is called a unique sink orientation, and we are interested in finding the unique sink of the whole cube, when the orientation is given implicitly. The basic operation available is the so-called vertex evaluation, where we can access an arbitrary vertex of the cube, for which we obtain the orientations of the incident edges. Unique sink orientations occur when the edges of a deformed geometric n-dimensional cube (i.e., a polytope with the combinatorial structure of a cube) are oriented according to some generic linear function. These orientations are easily seen to be acyclic. The main motivation for studying unique sink orientations are certain linear complementarity problems, which allow this combinatorial abstraction (due to Stickney and Watson, 1978), where orientations with cycles can arise. Similarly, some quadratic optimization problems, like computing the smallest enclosing ball of a finite point set, can be formulated as finding a sink in a unique sink orientation (with cycles possible). For acyclic unique sink orientations, randomized procedures due to Bernd Gartner (1998, 2001) with an expected number of at Most e/sup 2/spl radic/n/ vertex evaluations have been known. For the general case, a simple randomized (3/2)/sup n/ procedure exists (without explicit mention in the literature). We present new algorithms, a deterministic O(1.61/sup n/) procedure and a randomized O((43/20)/sup n/2/)=O(1.47/sup n/) procedure for unique sink orientations. An interesting aspect of these algorithms is that they do not proceed on a path to the sink (in a simplex-like fashion), but they exploit the potential of random access (in the sense of arbitrary access) to any vertex of the cube. We consider this feature the main contribution of the paper. We believe that unique sink orientations have a rich structure, and there is ample space for improvement on the bounds given above.