Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.