Input: | An oracle for a function
s: {0,1} defining a
US-orientation of the graph of the ^{d} ¾® {+,-}^{d}d-cube |
---|---|

Output: | The sink of the orientation |

Status (general): | Open |
---|---|

Status (fixed dim.): | Constant time |

Szabó and Welzl [63] describe a randomized algorithm
solving the problem in an expected number of
O(a oracle calls with
^{d})a=sqrt(43/20)<1.467 and a deterministic algorithm that
needs O(1.61 oracle calls. Plugging an optimal algorithm
for the three-dimensional case (found by Günter Rote) into their
algorithm, Szabó and Welzl even obtain an ^{d})O(1.438
randomized algorithm.
^{d})The problem not only generalizes Problem 28, but also certain linear complementary problems and smallest enclosing ball problems. In fixed dimension the problem is trivial by mere enumeration. |

Related problems: | 28 |
---|