1
$\begingroup$

Let $C \subset R^n$ be the convex hull of the set of points $C' \subset R^n$ such that for every $c \in C'$, $c_i \in \{0,1\}$. Let $b \not \in C$. Is there an algorithm that will generate the closest (by euclidean distance) $c^\ast \in C$ to $b$?

  • 3
    Can you fix your notation? For instance, what does "c_i = 1/0" mean? Generally, expressions like "1/0" strike fear in the hearts of mathematicians. If this means that c_i is either 1 or 0, then C' is just the unit n-cube.2011-12-29
  • 0
    Yes, i just mean that $c_i$ is either 1 or 0, and so $C'$ is the unit n-cube.2011-12-29
  • 1
    And if $C$ is indeed a hypercube, then you can get the closest point in $C$ to an arbitrary point $b$ simply by clamping each coordinate of $b$ to the range $[0,1]$.2011-12-29
  • 0
    I'm sorry but I don't know what 'clamping' means here. Thanks.2011-12-29
  • 1
    I believe by 'clamping', @RahulNarain simply means that if the coordinate is greater than 1 make it 1, if it is less than 0 make it 0, and otherwise leave it as is. This makes intuitive sense if you can visualize it in two or three dimensions.2011-12-29
  • 0
    The closest point may not be a vertex of the cube.2011-12-29

3 Answers 3