Unique sink orientations of cubes.pdfVIP

Unique Sink Orientations of Cubes Tibor Szabo?  Emo Welzl Theoretical Computer Science, ETH Zu?rich CH-8092 Zu?rich, Switzerlandfszabo,emog@inf.ethz.ch Abstract Suppose we are given (the edge graph of) an n- dimensional hypercube with its edges oriented so that ev- ery 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 de- formed geometric n-dimensional cube (i.e., a polytope with the combinatorial structure of a cube) are oriented accord- ing to some generic linear function. These orientations are easily seen to be acyclic. The main motivation for study- ing unique sink orientations are certain linear complemen- tarity problems, which allow this combinatorial abstraction (due to Alan Stickney and Layne Watson), where orienta- tions with cycles can arise. Similarly, some quadratic op- timization 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 proce- dures due to Bernd Ga?rtner with an expected number of at most e2pn vertex evaluations have been known [3, 4]. For the general case, a simple randomized (3=2)n procedure ex- ists (without explicit mention in the literature). We present new algorithms, a deterministic O(1:61n) procedure and a randomized O((43=20)n=2) = O(1:47n) procedure for unique sink orientations. An interesting aspect of these al- gorithms is that they do not proceed on a path to the sink (in a simplex-like fashion), but they exploit the potential of ran- dom access (in the sense of arbitrary access) to any vertex of the cu