# Algorithm for shifted center of mass calculation

Imagine that we have a set of points with defined x coordinate and mass for each of them: {($x_i$, $m_i$)}.

Canonical center of mass is a point $x_0$ that divides points to the left ones and the right ones in such way that
$\sum_{left} m_i |x_i-x_0| = \sum_{right} m_i |x_i-x_0|$

Now I need to find such point $x^*$ (shifted center of mass) that
$\lambda \sum_{left} m_i |x_i-x^*| = \mu \sum_{right} m_i |x_i-x^*|$ , where $\lambda + \mu = 1$

Does anybody know an efficient algorithm for shifted center of mass calculation?

-

Effectively you're weighting the masses of the points to the left by $\lambda$ and those of the points to the right by $\mu$. If you already knew where the split will be, i.e. which points will be to the left and which ones will be to the right, you could just calculate the standard centre of mass with the weighted masses $\lambda m_i$ and $\mu m_i$, respectively. The only problem is that this might lead to a different split point between left and right than you'd assumed.

Two ways of solving this come to mind. The easiest would be to just iterate, using the left/right split that the previous step produced to assign the weights in the next step, until the split no longer changes. A slightly more elaborate approach would be a binary search that zeros in on the correct split point by in each step halving the interval of indices in which it could lie. Note that this approach relies on the fact that the weighted center of mass moves monotonically as you change the split point, so you always know on which side you're erring. I suspect which of the approaches is more efficient may depend on your points and weights.

-
Thank you, binary search worked perfect for this! And additional thanks for noticing that center of mass moves monotonically. –  levanovd Apr 7 '11 at 6:15
You're welcome; glad it worked. –  joriki Apr 7 '11 at 7:09

This is a one-dimensional root finding problem, covered in any numerical analysis text. Chapter 9 of Numerical Recipes(free if you check the obsolete versions) has C code for several methods.

-