algorithm - Springs and Hooks -

okay,

i dealing problem, can't seem solve. little ?

problem: given wooden line of length m has n hooks , positions of these hooks given array ( 0 < p < m ). there spring attached each hook , each spring has metal ball @ other end. balls of same radius, r , same mass m. springs have same stiffness coefficient. how find optimum position of balls such springs , system in equilibrium ? metal balls not allowed go before or after line. i.e ends of balls cannot < 0 or > m. possible have multiple hooks @ same position in array.

assumptions: given array valid.

you can ignore vertical stretch , consider stretch of spring in horizontal directions. problem can seen 1d in nature then.

limits: o(nlogn) solution or better sought here.

example: m = 10, array = [ 4, 4 ], r = 1 ( diameter 2 ), optimum ball position = [ 3, 5 ]

what i've tried far:

• take 1 hook/ball @ time, create clustors if 2 balls hit each other. place them symmetrically @ centroid of hooks. bottleneck o(n^2) since balls keep hitting each other
• put balls @ complete centroid of hooks. return max of 3 sub-problems recursively.. a) balls being stretched left, b) balls being stretched right, c) balls in middle of these. bottleneck 3 subproblems may have overlaps , getting overlaps seems awkward.

here sort of binary search find correct position of each of balls.

1. start balls next each in order of connections farthest left each can go.
2. calculate amount of space have balls move (the distance right-most ball right edge), , use half of starting increment.
3. calculate net force on each ball spring, neighbors, , edges.
4. move each ball increment in direction of net force on it, or keep if there no net force.
5. if increment below precision want or balls had no net force on them, stop. else, divide increment 2 , go step 3.