<h3>Time $O(d^3\log d)$</h3>

<p><strong>lemma:</strong> <em>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).</em></p>

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

<p>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$.  </p>

<p>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$.</p>

<p>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</p>

<p>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.  </p>

<p>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)$.</p>

<h3>Time $O(d^2\log d)$</h3>

<p>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)$.</p>

<h3>Faster?</h3>

<p>To make discussion easier, let's rephrase the problem as follows.  <em>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.</em>  (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)$.)</p>

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

<p>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.</p>

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

CC BY-SA 3.0
2012-12-26T11:43:07.980Z
Thanks Neal. Can one improve on Dijkstra-like corner expansion ? The sets of possible nearest d+1 corners after normalization (flipping x to <= 1/2 and sorting) appear to grow very slowly with d.
Denis
CC BY-SA 3.0
2012-12-27T16:47:14.553Z
I edited the answer to discuss run time more explicitly.
Neal Young
CC BY-SA 3.0
2012-12-28T00:58:05.307Z
And David's answer shows how to get it down to $O(d\log d)$.
Neal Young
CC BY-SA 3.0
2012-12-24T16:39:02.237Z
2012-12-27T16:46:53.163Z
2012-12-27T16:46:53.163Z
Neal Young
<p>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).</p>

<p>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).</p>

<p>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)$.</p>

<p>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)$.</p>

CC BY-SA 3.0
2012-12-28T00:57:03.463Z
I agree with David's solution: the binary tree that he describe suffices to reach all the sets, giving $O(d\log d)$ time.
Neal Young
CC BY-SA 3.0
2012-12-27T20:21:06.367Z
2012-12-27T21:22:15.037Z
2012-12-27T21:22:15.037Z
David Eppstein
<p>In practice, weights are often distributed uniformly, roughly ~ 1 2 3 $\dots$<br>
Then a simple heuristic is to start with:<br>
$\qquad$ the $d$ single bits, e.g. 10000000 01000000 $\dots$ 00000001<br>
$\qquad$ $\lceil ln_2 d\rceil$ low-bit combinations
00000011 00000101 00000110 00000111<br>
$\qquad$ few-bit combinations of the next $\lceil ln_2 d\rceil$, e.g.
00001001 00001010 00001100 .<br>
The best $d+1$ of these candidates works pretty well in practice,
at least for small $d$.</p>

CC BY-SA 3.0
2012-12-28T12:04:35.593Z
2012-12-28T12:04:35.593Z
Denis
<p>How can one find the $d+1$ corners of the unit cube in $\mathbb{R}^d$
nearest a point $x$ in the cube ?<br>
Use the L1 metric, so that in 4d 
|$x$ - 0000| = $\sum {x_i}$,
|$x$ - 0001| = $x_3 + x_2 + x_1 + (1 - x_0)$<br>
($x_0$ on the right) and so on.</p>

<p>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.<br>
Define $c \equiv 1 - 2x$, $ 1\geq c_{d-1} \geq \dots\  c_1 \geq c_0 \geq 0$.<br>
Then we want the $d+1$ corners with smallest $c \cdot$ corner.</p>

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

<pre><code>    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
</code></pre>

<p>However in 5d, 6d ... the trees of increasing corners look (to me)  increasingly messy.<br>
Heuristics for approximate-nearest would be fine.</p>

CC BY-SA 3.0
2012-12-23T21:30:59.650Z
What breaks in the straightforward approach? Assume that each corner of the cube is in $\{0,1\}^d$ and $x\in [0,1]^d$. Round each coordinator to the nearest integer to get the closest point $p$, and generate $d$ more "closest points" by adding $1\mod 2$ to each coordinate of $p$, independently.
Daniel Apon
CC BY-SA 3.0
2012-12-24T10:58:23.303Z
@Daniel Apon, in 3d with 0 <= x2 <= x1 <= x0 <= 1/2 or 1 >= c2 >= c1 >= c0 >= 0 as above, the nearest 4 corners can be 000 001 010 100 as you suggest, but can also be a face 000 001 010 011. (The whole 3d cube splits into 8 + 6 pieces, 8 corner-plus-adjacent and 6 faces.)
Denis
CC BY-SA 3.0
2012-12-25T19:18:38.840Z
Here's another way to state this problem:  given a collection of $n$ non-negative numbers, find the $n+1$ minimum-cost subsets (where the cost of a set is the sum of the numbers in it).
Neal Young
CC BY-SA 3.0
2012-12-26T13:41:30.443Z
Yes, that's the min c . corner above -- min-cost subset is a better name, add that to the title / tags ?
Denis
<ds.algorithms><approximation-algorithms><heuristics>
Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$
Denis
# Find the nearest $d+1$ corners of a cube in $\mathbb{R}^d$

(Asked by: username_0 on 2012-12-23)

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.

**Tags:** ds.algorithms, approximation-algorithms, heuristics
> **Comments:**
> **username_1**: What breaks in the straightforward approach? Assume that each corner of the cube is in $\{0,1\}^d$ and $x\in [0,1]^d$. Round each coordinator to the nearest integer to get the closest point $p$, and generate $d$ more "closest points" by adding $1\mod 2$ to each coordinate of $p$, independently.  
> **username_0**: @Daniel Apon, in 3d with 0 <= x2 <= x1 <= x0 <= 1/2 or 1 >= c2 >= c1 >= c0 >= 0 as above, the nearest 4 corners can be 000 001 010 100 as you suggest, but can also be a face 000 001 010 011. (The whole 3d cube splits into 8 + 6 pieces, 8 corner-plus-adjacent and 6 faces.)  
> **username_2**: Here's another way to state this problem:  given a collection of $n$ non-negative numbers, find the $n+1$ minimum-cost subsets (where the cost of a set is the sum of the numbers in it).  
> **username_0**: Yes, that's the min c . corner above -- min-cost subset is a better name, add that to the title / tags ?  

---

## 3 answers

### Answer by username_2 on 2012-12-24. Score: 8 | Accepted answer

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

> **Comments:**
> **username_0**: Thanks Neal. Can one improve on Dijkstra-like corner expansion ? The sets of possible nearest d+1 corners after normalization (flipping x to <= 1/2 and sorting) appear to grow very slowly with d.  
> **username_2**: I edited the answer to discuss run time more explicitly.  
> **username_2**: And David's answer shows how to get it down to $O(d\log d)$.  

---

### Answer by username_3 on 2012-12-27. Score: 8

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)$.

> **Comments:**
> **username_2**: I agree with David's solution: the binary tree that he describe suffices to reach all the sets, giving $O(d\log d)$ time.  

---

### Answer by username_0 on 2012-12-28. Score: 0

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$.


---

