Applet: Unique Sink Orientation

Instruction

  1. Choose "3-cube" or "4-cube" or "5-cube".
  2. Press "random generation".
    (5-cube takes some time (about 30 seconds).)
  3. "Evaluation: 0" will appear.
  4. Click vertices and find the sink.

  5. If you press "show whole orientation", then you can look at the whole orientation on the cube.
  6. If you press "show vertices", then you can look at the labels of the vertices (which will help you to find an antipodal vertex).
  7. If you press "show outmap", then you can look at the out-map of the given unique sink orientation.
    The out-map s of an orientation is a map assigning to each vertex the set of all the directions of the out-going edges from this vertex.
    A sink can be characterized as a vertex v such that s(v) is empty.

What is the Unique Sink Orientation?

Consider a polytope (i.e., a bounded convex polyhedron). Then, assign an orientation to each edge of this polytope. A unique sink orientation is such an orientation that every face has a unique sink. At moment, we consider only a unique sink orientation of d-dimensional cubes. An example of a unique sink orientation of cubes is linear programming problem. When we consider a generic linear function over a polytope combinatorially equivalent to a cube, then this gives rise to a unique sink orientation. The smallest enclosing ball problems and a class of the linear complimentarity problems also yield unique sink orientations of a cube.

The Unique Sink Orientation Programming is a problem to find, when a unique sink orientation is given, the sink of this orientation. In this problem, a unique sink orientation is given by an oracle, and when we evaluate a vertex then the oracle gives us the orientations of the edges incident to the evaluated vertex. In this situation, we want to find a good algorithm which requires as small number of evaluations as possible until we evaluate the sink. (Note that even if we can tell where is the sink by the orientation, we must 'evaluate' the sink itself.) Szabo and Welzl showed that for 3-cubes an optimal deterministic algorithm needs at most 5 evaluations, and for 4-cubes an optimal deterministic algorithm needs at most 7 evaluations. For 5-cubes, FibonnaciSeesaw Algorithm by Szabo and Welzl takes at most 13 evaluations, but this is not known optimal.

Note (added on March 28, 2002)

I. Schurr noticed that the generation method that I use is not a uniformly random generation of the unique orientations. I am going to change the method, soon or later.

Reference

[Top]
okamotoy@jaist.ac.jp