The Voronoi cells are permutohedra: https://en.wikipedia.org/wiki/Permutohedron On Tue, Feb 2, 2016 at 4:01 PM, Dan Asimov <asimov@msri.org> wrote:
In the case of n = 3, we need to figure out which hexagonal Voronoi region a given triple (x,y,z) is in.
As n increases beyond 3, the Voronoi regions become increasingly complicated polytopes.
Suppose n is 30. The number of possible ways to round up or down each of 30 numbers is over a billion. Maybe there's a faster way to decide which Voronoi region (x_1,...,x_30) belongs to.
Then again, maybe not.
—Dan
On Feb 2, 2016, at 3:44 PM, Tom Rokicki <rokicki@gmail.com> wrote:
In answer to (1), defining "good" as "fast", the appropriate algorithm is "round, determine total error (say, +e), "e" values to round the other way selecting those with the least individual error". This is a linear-time algorithm. Did you have another idea for what "good" might mean here?
In this case minimizing sum of absolute error and minimizing sum of squared error is the same.
On Tue, Feb 2, 2016 at 3:22 PM, Dan Asimov <asimov@msri.org> wrote:
Suppose we have a finite sum of nonnegative numbers that equals 1:
(*) x_1 + ... + x_n = 1
.
Because TV viewers are so easily confused by several digits beyond the decimal point, we want to convert (*) to a sum of integer percentages P_j in the most felicitous, or the least infelicitous, way:
P_1 + ... + P_n = 100%
For example let n = 3. Then we want to map the points on the triangle
{(x,y,z) in (R_0)^3 | x + y + z = 1}
to the discrete set of 5151 points
{(M,N,P) in (Z_0)^3 | M + N + P = 100}
(where R_0 and Z_0 denote the nonnegative reals and integers, respectively).
One obvious thing to try is to minimize the sum of squared error:
So let
(**) E(M,N,P) = (x-M)^2 + (y-N)^2 + (z-P)^2
and pick (M,N,P) such that E(M,N,P) is minimized.
For the sake of this question, let's ignore the measure 0 of cases where the (M,N,P) minimizing (**) is not unique.
Questions: ----------
1. Let n > 0 be arbitrary. Is there a good algorithm for applying (**) in practice, to get the quantization (x_1,...,x_n) |—> (P_1,...,P_n) ???
2. Is there a better or more useful measure of error than sum of squared differences? If so, why is it better?
—Dan _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- [ <http://golly.sf.net/>Golly link suppressed; ask me why] -- _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Mike Stay - metaweta@gmail.com http://www.cs.auckland.ac.nz/~mike http://reperiendi.wordpress.com