Carnival of Mathematics #67

The 67th Carnival of Mathematics is up. Awesome stuff there, so go check it out.

Something caught my attention. James Grime created a video of a math puzzle involving two trains and a fly. Hmm… sounds familiar…

Then there’s the video with the solution:

That sounds really familiar…

Bzzz…

Help! Getting a “nice” reverse engineered Bézier curve

Commenter Timo wants to know how to get a nice shape for a reverse engineered Bézier curve.

The question started from calculating the control points of a cubic Bézier curve if you’re given 4 points that lie on the curve, assuming the first and last given points were also the first and last control points. I wrote a similar article for a quadratic Bézier curve too.

To sum up, you have 1 degree of freedom when working on a quadratic Bézier curve. In the case of a cubic Bézier curve, you have 2 degrees of freedom, meaning 2 variables in the calculation that you have to decide on. Now this posed a problem, because there are an infinite number of solutions. How do you decide on a numeric value?

Well, for a quadratic Bézier curve, the simplest and obvious option is to choose the second given point (since the first and last control points are determinable) to be at the halfway mark. For a cubic Bézier curve, the second and third given points are chosen to be at the 1/3 and 2/3 mark along the curve respectively. Now this may or may not be suitable, but it does give you something to start with.

I want to state right now, that I had not been doing formal mathematics for a while. There is a limit to what I know, and I’m not an expert. I just know enough to figure out how to solve problems. Sometimes, it’s not enough. Keep that in mind.

“Nice curve” is subjective

Now Timo’s problem is getting a better shaped cubic Bézier curve from those calculations. Since the 4 given points are fixed, and the first and last control points are also fixed, the only thing you can manipulate are the second and third control points. Which in turn means deciding on values of u and v to get a “nice” cubic Bézier curve in the end.

This, “niceness”, is a subjective criteria. How do you determine if a cubic Bézier curve looks nice? Remember that we don’t have the control points yet. So we don’t know how the curve looks like. So we don’t even know if manipulating the second and third control point to not be at 1/3 and 2/3 will result in a nice curve. It’s a chicken and egg problem.

Apportioned chord length

During the correspondence with Timo, some solutions were discussed. The next simplest set of values to try for u and v are calculated based on the given points.

Let d1 be the distance between the first and second given point.
Let d2 be the distance between the second and third given point.
Let d3 be the distance between the third and last (fourth) given point.

Then let u = d1/(d1 + d2 + d3) and v = (d1 + d2)/(d1 + d2 + d3). This should result in a curve that’s “better shaped” than the (u,v) pair (1/3, 2/3). When I wrote that article for the cubic curve version, this was the next default set of values for u and v, but I didn’t want to add too much more. Well, nobody asked, so I left it as it was.

It turns out that Don Lancaster already wrote about it. He called it “apportioned chords” method.
http://www.tinaja.com/glib/nubz4pts1.pdf

Inflection points

Then Timo had another problem. He wanted the second and third given points to also lie at the “loop tips”. What are loop tips? After some clarification, I believe Timo is referring to the inflection points on the curve. An inflection point

is a point on a curve at which the curvature (second derivative) changes signs. The curve changes from being concave upwards (positive curvature) to concave downwards (negative curvature), or vice versa.

A cubic Bézier curve can have 0, 1 or 2 inflection points. If it’s a straight line, it has 0. If it’s U-shaped, it has 1. And if it zigzags, it has 2. And Adrian Colomitchi proved that there are at most 2 inflection points on a cubic Bézier curve.

As you can see, inflection points don’t necessarily have to coincide with the given points.

By the way, I used Paint.NET for the illustration. I took a screenshot of me drawing the curve, still with the given points visible (noted by the small squares). Paint.NET appears to have succeeded in doing the very thing Timo wants, to render a cubic Bézier curve using 4 given points. Of course, I’m assuming the image editor is using cubic Bézier curves…

The math paper

I found another reference with a more explicit mathematical formulation to help Timo.
http://www.cis.usouthal.edu/~hain/general/Publications/Bezier/bezier%20cccg04%20paper.pdf

As of this writing, page 3 of that paper explicitly shows the calculation needed to find the inflection points of a cubic Bézier curve, if they exist. Let me emphasise that again. The curve might have only 1 inflection point, or none.

Maximum curvature

Then Timo found another forum posting for the fast calculation of maximum curvature. An inflection point would have the “maximum curvature”. The problem with that solution is that it assumes we have the control points.

So my suggestion was to do iteration. Use my method to get a set of control points. Perhaps use the apportioned chords to start off with a good set of control points. Then apply the maximum curvature solution to find the inflection points and the associated values of t. With those values of t, pump them back into my method to find a new set of control points. Pump those control points into the maximum curvature solution to find inflection points and their t values. Iterate till the t values between iterations are within acceptable margins of error.

Caveat: I don’t know if this combination of 2 algorithms in an iterative manner will converge. I have not tested this. Use at your own risk.

Scaling up to 3 dimensions

Anyway, Timo found another solution himself (he didn’t say what though). He still needed to handle that cusp point. What cusp point, you ask? It’s in page 3 of that paper I mentioned above. That paper is for 2 dimensional cubic Bézier curves. The degree of the curve is independent of the degree of the dimensions. Timo wants to know how the 3 dimensional case will look like.

Now, the method of finding inflection points is to do a cross product of the first derivative and second derivative of the cubic Bézier curve equation. The Bézier curve is parametrised into

x(t) = ax * t^3 + bx * t^2 + cx * t + dx
y(t) = ay * t^3 + by * t^2 + cy * t + dy

and using the Bézier basis matrix, the coefficients are

ax = -x0 + 3*x1 – 3*x2 + x3
bx = 3*x0 – 6*x1 + 3*x2
cx = -3*x0 + 3*x1
dx = x0

ay = -y0 + 3*y1 – 3*y2 + y3
by = 3*y0 – 6*y1 + 3*y2
cy = -3*y0 + 3*y1
dy = y0

Set the cross product to 0. The inflection points are found at values of t when you solve that equation:

x’ * y” – x” * y’ = 0

where x’ and x” are the first and second derivatives of x(t). Similarly for y’ and y”. The solution is in that paper I mentioned before.

This is if the curve is in 2D. The cross product of 2D vectors is a scalar. And we set the scalar to 0 to solve for t. The cross product of 3D vectors is a vector, and so we’re solving with a zero vector.

So with
z(t) = az * t^3 + bz * t^2 + cz * t + dz
for the third dimension, we have

x’ = 3 * ax * t^2 + 2 * bx * t + cx
y’ = 3 * ay * t^2 + 2 * by * t + cy
z’ = 3 * az * t^2 + 2 * bz * t + cz

x” = 6 * ax * t + 2 * bx
y” = 6 * ay * t + 2 * by
z” = 6 * az * t + 2 * bz

The cross product is the determinant of the following

where i, j, k are the unit vectors. I’ll leave it to you to find out the formula for the determinant of a 3 by 3 matrix.

So we’re going to solve this:
0 = (y’ * z’’ – z’ * y’’) * i – (x’ * z’’ – z’ * x’’) * j + (x’ * y’’ – y’ * x’’) * k
where 0 is the zero vector.

This implies that

y’ * z’’ – z’ * y’’ = 0
x’ * z’’ – z’ * x’’ = 0
x’ * y’’ – y’ * x’’ = 0

This time the zeroes are scalars. We now have 3 times the number of equations to solve when compared to the 2D case. This means there are potentially 6 values of t for the inflection points to check. Hopefully, there will be repeated values of t. Hopefully, the number of unique values of t is 2 or less (remember Adrian’s proof?).

If a t value is repeated, it’s probably an inflection point. What if we get 6 unique values? Is a 6-unique-value case even possible? I don’t know. You’ll have to interpret the values in the best way you can, based on some assumptions and arguments.

What do you think?

So after reading through that entire article, what do you think? Comments on the methods I described? Do you have a new method? Your thoughts on whether this problem is even solvable? That I’m a complete idiot?

Let me know in a comment. Or better, write a blog post and tell me about it. Because if it took me that long to explain the solutions, your solution is probably just as long. It’s a Bézier curve. A picture might be appropriate.

Percentage contribution over the long-term

Some time ago, I received an unusual request for help from a stranger via email. It was something of a financial nature, and I felt incapable of answering it fully. So I turned to Christopher, my engineer friend who’s also versed in finance, for help. I felt that the stranger’s request was quite personal, and I wasn’t sure if the stranger wanted the request to be publicised here on the blog. So to protect the innocent, I will wrangle the original problem to be most indecipherable. However, the solution given by Christopher was worth mentioning.

On to the problem then. We shall stick only to money as the sole source of contribution. Emotional and effort labour are just as important, but it’s difficult to quantify them mathematically. We’ll even ignore time labour. It’s not fair, but the world sometimes operate that way, so we’ll just accept it as best as we can.

Suppose there are 2 partners in a new business. Each of them contributes a different amount of money each month to the business, and may even contribute variably across each month. The money is used to maintain the business (for example, settle any bank loans, pay salaries, web site hosting costs, marketing expenses, product creation costs, utility bills and so on). After say 3 years, they want to sell off the business and liquidate their assets in it.

How much should each business partner take from that lump sum of money (from selling the business), based solely on their monetary contribution over the years?

The main problem of using a simple summation of their monetary contributions and calculating a percentage based on that, is inflation. $100 contributed in the 1st month is worth more than $100 contributed in the 37th month (4th year, 1st month).

Christopher suggested abiding by a yearly rate for the purpose of inflation, in particular, using government bonds as the rate. To add stability to the rate, he suggested using the 10-year bond rate. The currency also matters. For our example, we’ll use the United Kingdom pound. Where you get that rate is up to you, as long as you feel it’s legitimate and correct, and that everyone agrees to using that rate. I got mine from Bloomberg (suggested by Christopher):

http://www.bloomberg.com/markets/rates/uk.html

[note: the above was correct as of time of writing this article. You are advised to go visit the Bloomberg site for the updated numbers. Or some other trusted site you know because you're probably more financially powerful than me.]

The rate is 3.51% for the 10-year yield.

The mathematical formulation

Let’s give our business partners names, Arianna and Ben.

Let s(i) be the “sum” at end of year i
Let x(i) be contribution of Arianna in year i
Let y(i) be contribution of Ben in year i
Let b(i) be bond interest rate in year i (3.51% is changed to 0.0351 without the percent).

Then s(i+1) = [1 + b(i)] * [s(i) + x(i) + y(i)]

Let cx(i) be sum contribution of Arianna, and cy(i) be sum contribution of Ben at end of year i.

Then cx(i+1) = [1 + b(i)] * [cx(i) + x(i)]
and cy(i+1) = [1 + b(i)] * [cy(i) + y(i)]

Then contribution percentage at end of year i of Arianna is
100 * cx(i) / s(i)

Contribution percentage at end of year i of Ben is
100 * cy(i) / s(i)

A short example (with numbers)

And a note. The numbers were picked out of thin air. I am not saying a man is better than a woman in the business arena. I need some numeric variation, and I just took it as the man contributing more. And the fact that I don’t want to search the stock photos for generic businessy settings with 2 people in them for hours. For some reason, it’s very hard to find a photo with 2 business people of the same gender. Then you wouldn’t be able to guess which one was which. I originally had Andy and Ben starring in my example.

Anyway…

Let’s say, in the 1st month, Arianna and Ben contribute £100 and £150 respectively. In the 2nd month, £200 and £100 respectively. In the 3rd month, £0 and £250 respectively. For the 1st year, Arianna and Ben contribute £1200 and £1800 respectively, for a grand total of £3000.

So at the start of the 2nd year, we look at the rate and say we find it’s 3.5%. Then we inflate their contributions by 3.5% to £1242 (1.035 * 1200) and £1863 (1.035 * 1800) respectively. We also inflate the sum total from £3000 to £3105.

Arianna and Ben continue to contribute to the business in the 2nd year. And at the end of the 2nd year, Arianna and Ben contributed £2100 and £1900 respectively (total £4000).

At the start of the 3rd year, we find the rate to be 3.52%. Here’s where it’s different. First we add the respective contributions to the previous inflated amounts. So we have £3342 (£1242 + £2100), £3763 (£1863 + £1900) and £7105 (£3105 + £4000) for Arianna, Ben and the sum total respectively. Then we inflate them by 3.52% to get £3459.64, £3895.46 and £7355.10.

For the 3rd year, Arianna and Ben contribute £2400 and £2600 respectively. And at the start of the 4th year, the rate is 3.51%.

Adding the sum contributions first, we get £5859.64, £6495.46 and £12355.10 for Arianna, Ben and sum total respectively. Inflating the numbers by 3.51%, we get £6065.31, £6723.45 and £12788.76. At this point, our business partners want to sell off their business, and they want to know what’s their percentage contribution.

So Arianna contributed 100 * 6065.31 / 12788.76 = 47.43%.
Ben contributed 100 * 6723.45 / 12788.76 = 52.57%

Further notes

I didn’t take care of rounding issues and decimal places in the example. I’ll leave that to you as an exercise. The most accurate method will be to store the values as they are, and only take them out for calculations at the final stage. Storing intermediate results might skew the accuracy if done over many iterations.

The other point is that you are free to calculate on a monthly basis instead of a yearly basis. The assumption is that the rate stays stable throughout the year, so a yearly rate is usable. If you’re inflating on a monthly basis, the contribution values will shoot up very quickly. They will not have any semblance to their original values. I want you to remember that the values are used to calculate the final percentage contribution, not the absolute contribution.

Contributing $40 out of $100 is 40%. Contributing $673.20 out of $1683 is also 40%. It’s relative.

[note to self: why didn't I think of using a currency with $, the generic dollar sign? I had to go pick the pound, and then had to replace all the monetary values in the example with the correct currency symbol...]

[UPDATE: the stranger found another of my article on percentage calculations. It must have made sense, because the stranger took that to mean I could help with the problem the stranger was facing. Yes, I'm using "the stranger" so you don't even know the gender. How's that for anonymity?]

[leading image by nyul]