| Input: | An oracle for a function s: {0,1}d ¾® {+,-}d defining a US-orientation of the graph of the 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(ad) oracle calls with
a=sqrt(43/20)<1.467 and a deterministic algorithm that
needs O(1.61d) 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 O(1.438d)
randomized algorithm.
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 |
|---|