Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$

Question

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.

Answer 1

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<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>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>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 (?).

Answer 2

It is equivalent to ask, among a set of $d$ non-negatively weighted items, for the $d+1$ subsets of minimum total weight. One can form all the subsets of the items into a tree, in which the parent of a subset is formed by removing its heaviest item (with ties broken arbitrarily but consistently); the $d+1$ solutions will form a subtree of this tree connected at its root (the empty set).

So, one can search this tree for the smallest $d+1$ items by a form of Dijkstra's algorithm in which we maintain a priority queue of subsets and remove them in priority order. We start with the first selected item being the empty set. Then, at each step, we maintain as an invariant of the algorithm a priority queue containing the next unselected child for each already-selected subset. When we select a set $S$, we remove it from the priority queue, and we add to the priority queue two new subsets: its first child (the set formed by adding the next heavier element than the heaviest element in $S$) and its next sibling (the set formed by removing the heaviest element in $S$ and adding the same next heavier element).

After sorting the items by their weights, it is straightforward to represent each set implicitly (as its heaviest element plus a pointer to its parent set), maintain the total weight of each set, and find the first child and next sibling needed by the algorithm in constant time per set. Therefore the total time is dominated by the initial sorting and by the priority queue operations, which take total time $O(d\log d)$.

Even this can be improved, if the items are already sorted by their weights. View the "first child" and "next sibling" relation from the previous algorithm as the left and right children in a binary tree of subsets. This tree is heap-ordered (total weight increases from parent to child) so we can apply an algorithm for finding the $d+1$ minimum-weight nodes in a heap-ordered binary tree [G. N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Computation, 104:197–214, 1993]. The total time, after the sorting step, is $O(d)$.

Answer 3

In practice, weights are often distributed uniformly, roughly ~ 1 2 3 $\dots$
Then a simple heuristic is to start with:
$\qquad$ the $d$ single bits, e.g. 10000000 01000000 $\dots$ 00000001
$\qquad$ $\lceil ln_2 d\rceil$ low-bit combinations 00000011 00000101 00000110 00000111
$\qquad$ few-bit combinations of the next $\lceil ln_2 d\rceil$, e.g. 00001001 00001010 00001100 .
The best $d+1$ of these candidates works pretty well in practice, at least for small $d$.