slice up a slice of a triangle into n areas of equal size

393 Views Asked by At

slices of a triangle

Figure description: The point $(0, 0)$ is in the upper left corner. The coordinate system grows to the lower right corner. The short sides of the big triangle have the same length.

I want to slice up the blue area in the drawing into $n$ parts of equal area $A$. I know the values of $x_0$ and $x_n$ and I want to know the values of $x_i$ where $0 < i < n$.

I solved it for $n = 2$:

$$A = \frac{x_1^2}{2} - \frac{x_0^2}{2} = \frac{x_2^2}{2} - \frac{x_1^2}{2}$$

$$\cdots$$

$$x_1 = \sqrt\frac{x_0^2 + x_2^2}{2}$$

But how do I solve this for any $n$?

Context: (Probably irrelevant for the mathematical problem.) The slices represent workload that I want to distribute to separate threads. Currently my program has 2 threads hard coded, but I want to make it configurable (because now I have an 8 core machine).

My program produces objects and then combines all the produces objects with each other to produce more objects. I distribute the combination operations across multiple threads. The blue area represents all combinations of the objects that where produces before (in the white area). The program stops if no new valid object can be created through combinations.

1

There are 1 best solutions below

2
On BEST ANSWER

As you note with the cases $i = 0$ and $i = 1$, for any $i < n$, $A = \frac{1}{2}(x_{i+1}^{2}-x_{i}^{2})$

But the area of the whole triangle minus the area of the white triange is $\frac{1}{2}(x_{n}^2-x_{0}^2)$ and A is one $n$th that area.

So we have: $\frac{1}{2}(x_{i+1}^{2}-x_{i}^{2}) = \frac{1}{2n} (x_{n}^2-x_{0}^2)$.

This gives: $x_{i+1} = \sqrt{\frac{1}{n} (x_{n}^2-x_{0}^2)+x_{i}^{2}}$

Hence knowing $x_n$ and $x_0$, you can iteratively generate $x_1$, then $x_2$ and so on.

Edit: Alternately, if you don't want to have to iterate ... for $j > i$, you have: $$\frac{1}{2}(x_{i+1}^{2}-x_{i}^{2})+\frac{1}{2}(x_{i+2}^{2}-x_{i+1}^{2}) + \cdot \cdot \cdot + \frac{1}{2}(x_{j}^{2}-x_{j-1}^{2}) = (j-i)A$$

$$ = \frac{1}{2} ( -x_i^2 +(x_{i+1}^2 -x_{i+1}^2) +(x_{i+2}^2 -x_{i+2}^2) + \cdot \cdot \cdot + (x_{j-1}^2 -x_{j-1}^2) + x_j^2)$$

$$= \frac{1}{2}(x_{j}^{2}-x_{i}^{2}) = (j-i)\frac{x_{n}^2-x_{0}^2}{2n}$$

Letting $i$ be zero:

$$= (x_{j}^{2}-x_{0}^{2}) = \frac{j}{n} (x_{n}^2-x_{0}^2)$$

Hence:

$$x_{j} = \sqrt{\frac{j}{n} (x_{n}^2-x_{0}^2)+x_{0}^{2}}$$