Jump to content

  • Log In with Google      Sign In   
  • Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at $59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.


Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!


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.

  • You cannot reply to this topic
2 replies to this topic

#1 luca-deltodesco   Members   -  Reputation: 637

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.

Sponsor:

#2 clb   Members   -  Reputation: 1792

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!

#3 luca-deltodesco   Members   -  Reputation: 637

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