Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$ How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?
Use the L1 metric, so that in 4d 
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + (1 - x_0)$
($x_0$ on the right) and so on.

For an alternate formulation,
first flip $x_i$ > 1/2 and sort, 
so that $ 0 \leq x_{d-1} \leq \dots\  x_1 \leq x_0 \leq$ 1/2;
by symmetry, an algorithm for this case can do any $x$ in the cube.
Define $c \equiv 1 - 2x$, $ 1\geq c_{d-1} \geq \dots\  c_1 \geq c_0 \geq 0$.
Then we want the $d+1$ corners with smallest $c \cdot$ corner.

In 4d for example, with $x_i$ decreasing 1/2 .. 0 as above,
the 5 nearest corners can be

    0 0 0 0
    0 0 0 1
    0 0 1 0

    0 1 0 0  or  0 0 1 1
                 0 1 * *

    1 0 0 0
 or 0 1 0 1


However in 5d, 6d ... the trees of increasing corners look (to me)  increasingly messy.
Heuristics for approximate-nearest would be fine.
Time $O(d^3\log d)$

lemma: Fix any $x\in[0,1]^d$.  Then there is a set $S$ containing $d+1$ corners of $\{0,1\}^d$ that are closest to $x$ and such that $S$ is connected (meaning that the subgraph of the hypercube induced by $S$ is connected).

Proof.
First consider the case that $x$ has no coordinates equal to $1/2$.

Given any corner $a$ in $S$, flipping a coordinate $a_j$ of $a$ will not increase the distance from $a$ to $x$ if $|a_j - x_j| \ge 1/2$.  

Consider any two corners $a,b$ in $S$ that differ in at least one coordinate $j$, and assume WLOG that $a_j=0$ and $b_j=1$.  If $x_j&lt;1/2$ then flipping $b_j$ in $b$ gives another point in $S$ (because it decreases the distance from $b$ to $x$).  Or, if $x_j&gt;1/2$ then flipping $a_j$ in $a$ gives a point in $S$.  Repeating this process for each differing coordinate in $a$ and $b$ gives a path connecting $a$ and $b$ within $S$.

If $x$ has coordinates equal to $1/2$, then, in choosing $S$, break ties among equidistant points by giving precedence to those with more zero coordinates.  Then the same argument will work.  QED

By the lemma, you can use a Dijkstra-like algorithm to find $S$.  Start with a corner closest to $x$ ($a$ with $a_j = 0$ if $x_j \le 1/2$).  Then repeatedly add to $S$ a corner that is closest to $x$ among those that are adjacent to some point in $S$.  Stop when $d+1$ points have been added.  

Naively (using a min-heap to find the next closest point to $x$ in each iteration), I guess there are $d+1$ iterations, and each iteration requires $O(d^2)$ work to generate the $d$ neighbors of the added node (each of which has representation of size $d$), giving run time $O(d^3\log d)$.

Time $O(d^2\log d)$

Represent each corner $a$ implicitly as a pair $(h, d)$, where $h$ is a hash of the set of indices $i$ such that $a_i=1$, and $d$ is the distance from $x$ to $a$.  From a given corner $a$, the pairs for all neighboring corners can be generated in $O(d)$ time (total).  This brings the run time down to $O(d^2\log d)$.

Faster?

To make discussion easier, let's rephrase the problem as follows.  Given a sequence of $d$ non-negative numbers $y_1 \le y_2 \le \cdots \le y_d$, find the $d+1$ minimum-cost subsets of the numbers, where the cost of a subset is the sum of the numbers in it.  (To see the connection with the previous problem, take $y_i = |x_i - 1/2|$; then each subset $Y$ of the $y_i$'s corresponds to a corner $a(y)$ of the hypercube, where $a_i(y)$ is 1 if ($x_i \le 1/2$ and $y_i\in Y$) or ($x_i&gt;1/2$ and $y_i\not\in Y$); and the cost of $Y$ is the distance from $x$ to $a(y)$.)

Here's a general idea for a faster algorithm.  Maybe somebody can figure out how to make it work.

Define an implicit directed graph where each node is a subset $Y$ of the $y_i$'s.  The start node is the empty set.  Represent the nodes implicitly as pairs $(h, c)$ where $h$ is the hash of the subset and $c$ is the cost.  For each subset $Y$, define the neighboring subsets somehow so that (i) if $Y\rightarrow Y'$ is a directed edge then the cost$(Y') \ge$ cost$(Y)$, and (ii) for any subset $Y'$, there is a directed edge $Y\rightarrow Y'$ from some subset $Y$ where cost$(Y) \le$ cost$(Y')$.  Then run Dijkstra's on this implicit graph starting at the start node.

Choose the edges (somehow) so that (i) and (ii) both hold, and the sum of the degrees of the cheapest $d+1$ nodes is $O(d)$.  (This is always possible, for example, take the edges to be those in some shortest-path tree rooted at the start.)  But can one define such a graph without a-priori knowledge of the shortest-path tree?  If so, this could lead to an $O(d\log d)$-time algorithm (?).