• Create Account

Awesome job so far everyone! Please give us your feedback on how our article efforts are going. We still need more finished articles for our May contest theme: Remake the Classics

# compute bounds on total value (intersecting plane with box in N dimensions)

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

2 replies to this topic

### #1luca-deltodesco  Members   -  Reputation: 625

Like
0Likes
Like

Posted 31 January 2012 - 08:50 AM

(NOT homework, don't worry)

We have a number payments of which we don't know the exact value.
And the number of payments which fit into a given disjoint set of ranges together with the percentage of the total value of payments, that payments from this range provide.

How can we compute the bounds on the total sum of payments?

For instance say that we know:

there are 4 payments in the range 0 <= x < 5
and 2 payments in the range 5 <= x < 20
and 2 payments in the range 20 <= x < 100

and that the payments in the range 0 <= x < 5 provide 10.7% of the total
payments in the range 5 <= x < 20 provide 27.7% of the total
and payments in the range 20 <= x < 100 provide 61.6% of the total

I think it should be clear we don't actually care about the value of specific payments, only their average within the range so that we can reason about the total value of payments in a given range, so that we would have:

0 <= X < 20
10 <= Y < 40
40 <= Z < 200

and that X = 0.107(X+Y+Z), Y = 0.277(X+Y+Z), Z = 0.616(X+Y+Z)

and we want to compute the upper and lower bounds of X+Y+Z.

It seems to me that the 3 equalities define a plane like:
(1/0.107 - 3)X + (1/0.277 - 3)Y + (1/0.616 - 3)Z = 0

and so we can find the upper/lower bounds of the total by intersecting the plane with the box defined by the inequalities, and at each interesting point (the lines intersecting the box) compute the total value and find the min/max of those to get the upper and lower bounds.

This would extend to any number of ranges in increasing dimensions, my only issue now is actually going about implementing this.

### #2clb  Members   -  Reputation: 1594

Like
0Likes
Like

Posted 31 January 2012 - 10:06 AM

Looks like this can be solved as an linear program, since the constraints and the function to optimize are both linear, and you are (I assume) modelling the average payments X, Y, Z as arbitrary scalars (and not as integers, or fixed-point rationals).
Me+PC=clb.demon.fi | C++ Math and Geometry library: MathGeoLib, test it live! | C++ Game Networking: kNet | 2D Bin Packing: RectangleBinPack | Use gcc/clang/emcc from VS: vs-tool | Resume+Portfolio | gfxapi, test it live!

### #3luca-deltodesco  Members   -  Reputation: 625

Like
0Likes
Like

Posted 31 January 2012 - 10:17 AM

Ahah, I hadn't thought of it that way. Guess I was stuck in my geometrical interpretation.

Thank you

Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

PARTNERS