5
$\begingroup$

If we consider a portion of the number line, say on the interval $[0,100]$, and split that into regions e.g. split at $80$ to create $2$ regions.

Now I want to subdivide the two regions. The region $[0,80]$ has $m$ partitions and the region $[80,100]$ has $n$ partitions. If $m = 2$ and $n = 10$ (for example), and the subpartitioning was done by splitting the region up equally, when we go from the first region to the second, the partition size is very different. What I want to do is blend the divisions between regions.

Suggestions on how I can do this (bearing in mind I'm not that good at maths) welcome!

EDIT: Sorry for being unclear. Picture should help. In this pic there's 2 regions divided into 2 and 4 (I couldn't easily draw 10 divisions!). The upper part shows equidistant splitting which is ignorant of what's happening in a neighbouring region. The lower part of the picture is roughly what I want. A key requirement is the nodes in the interval $[80,100]$ go from having larger spacing to smaller spacing the further they get away from the interval $[0,80]$. If there was 10 nodes within $[80,100]$, they'd be mainly bunched up towards 100 and the gaps between the nodes would get progressively smaller. The larger spacing is because of the large division size in the neighbouring interval.

The number line could be split up into any number of regions, and the number of divisions on each region is not chosen by me, but imposed on me. One region would affect adjacent regions only.

Blend pic

  • 0
    @Rahul: Something to control the transition would be the icing on the cake. It's almost like for a given region, part of the left hand side region's spacing (width / divisions) is apportioned to the division in this region in diminishing quantities. Of course, there is only enough space in this region, so it's "normal" division size is smaller further away from the left hand side region. That alone is more complex than I can solve. Then, there's the right hand side at play too...2012-03-09

3 Answers 3

2

Do you get to choose $m$ and $n$ or are they fixed? If you get to choose them, they should in the ratio of the sizes of the initial intervals. So if you have $[0,80]$ and $[80,100]$ and you want $m+n=12$, you should choose $m=10,\ n=2$ to get the first intervals $8$ and the second ones $10$.

If $m$ and $n$ are given you could imagine having the sub-intervals in arithmetic progression. The subintervals in the first are $a, a+d, a+2d \ldots a+(m-1)d$ where $d$ can be negative if you want. The sum of these is $ma+m(m-1)d/2$, which in your case should be $80$. Using $b$ and $e$ for the second interval, you have $nb+n(n-1)e/2$ for the sum, which should equal $20$. So you have to choose $a,b,d,e$ so that $ma+m(m-1)d/2=80$

$nb+n(n-1)b=20$

$a+(m-1)d \approx b$

Or maybe you want the steps to continue, in which case you could ask that $a+md=b$

This is three equations in four unknowns, so you should have a single degree of freedom left. However, if you have a big mismatch (as in your example) between the average subintervals, the subintervals may become negative.

  • 0
    $m$ and $n$ are fixed externally. I've edited the original post to show that a region would not necessarily be divided into equal parts.2012-03-08
2

This looks like a problem where interpolation could be a useful tool. I'll illustrate some different properties of the partition you can capture, starting with the simplest case.

Suppose the whole interval in question is $[a,b]$, which is divided at some point $c$ in the interval. We partition the subinterval $[a,c]$ into $m$ equal parts, and the subinterval $[c,b]$ into $n$ equal parts.

interval drawing

We want to "smooth" the interval out in some way. Well, we could start by only caring about the total number of subintervals, $m+n$. Then we just divide the interval $[a,b]$ into $m+n$ equal parts. But that's not very satisfying.

Instead, let's take into account the sizes of the original partitions. At the very least we can keep the first and the last partitions the same size as they were when we rescale. Now, wouldn't it be nice if we could just make a function that would give us the endpoints of the $n^{\text{th}}$ partition when we plug in $n$? What properties would we want this function to have? Well, we would need it to start at $a$, so $f(0) = a$. And, as we said, we want it to fix the length of the first partition, so we want $f(1) = a + (c-a)/m$, which is the length of the first partition. We also want it to fix the length of the last partition, so we need to fix its endpoints at $b - (b-c)/n$ and $b$. To recap, we want

  1. $f(0) = a,$

  2. $f(1) = a + (c-a)/m,$

  3. $f(m+n-1) = b - (b-c)/n,$

  4. $f(m+n) = b.$

We want the rest of the partitions to just smooth themselves out between these two, so we'll draw a simple smooth curve through these data points and be done with it. To do this, we'll find the interpolating polynomial (the Lagrange interpolating polynomial has a particularly straightforward form) for these points. It's easy in Mathematica:

InterpolatingPolynomial[{{0,a},{1,a+(c-a)/m},{n+m-1,b-(b-c)/n},{n+m,b}},x] 

This returns

$f(x) = a+x \left(\frac{b-a}{m+n}-\frac{[b m+a n-c (m+n)] [(n-1) (m+n)+(m-n) x] (m+n-x)}{m n (m+n) (m+n-1) (m+n-2)}\right).$

The results are generally OK. Let's take $a=0$ and $b=100$ as in your example. Now, $c=80$, $m=2$, and $n=10$ is a little extreme, and this polynomial doesn't behave well in that case. Here are some other examples, where the red dots are the original partitioning and the blue dots are the rescaled partitioning.

$c=80$, $m=2$, $n=6$:

80-2-6

$c=50$, $m=2$, $n=9$:

50-2-9

$c=20$, $m=6$, $n=6$:

20-6-6

Generally the results are best the closer the original distribution is to completely uniform.

Now, we may also wish to keep the same number of partitions on either side of $c$. That is, if the original partitioning has $m$ partitions to the left of $c$ and $n$ to the right, we want the rescaled partitioning to do the same. So, on top of conditions (1)-(4) we had earlier, we also want $f(m) = c$, so that the $m^{\text{th}}$ partition ends at $c$. Let's also require that the $m^{\text{th}}$ partition has a length which is the average of the lengths of the first and the last partitions. That is, we want $f(m-1) = c - (n (c - a) + m (b - c))/(2 m n)$. In Mathematica:

InterpolatingPolynomial[{{0,a},{1,a+(c-a)/m},{n+m-1,b-(b-c)/n},{n+m,b},{m,c},{m-1,c-(n (c-a)+m (b-c))/(2 m n)}},x] 

The polynomial it gives is pretty ugly, so I'll leave it out. Here are some examples:

$c=80$, $m=4$, $n=5$:

ex2-80-4-5

$c=50$, $m=14$, $n=5$:

ex2-50-14-5

$c=30$, $m=6$, $n=6$:

ex2-30-6-6

The results are a little weird sometmes but they retain more of the structure of the original partitioning than the earlier example. So I guess it depends on what you need.

  • 0
    @JosephGarvin these were plotted using Mathematica. If you would like I can try to find the code I used to make them, though I can't promise I'll find it since I made them almost a year ago!2013-01-27
0

One possibility is to put the lengths of the intervals in geometric progression. You do this by selecting a number $r$ and making the length of each interval (after the first one) $r$ times the length of the previous interval. In your example, if you start your first interval at $0$, you would want to set $r$ to some value between $0$ and $1$ in order to make the "higher" intervals smaller.

If the length of the lowest interval is $a$ and you have $m+n$ intervals altogether, the total length of all intervals together will be $ \frac{a(1 - r^{m+n})}{1-r}. $ But you want to divide this series into two parts, one starting with an interval of length $a$ and the next starting with an interval of length $a^m$. Your constraint is that the first $m$ intervals have to have some predetermined sum, $S$, and the last $n$ intervals have to have the predetermined sum $T$. This gives us two equations: \begin{align} \frac{a(1 - r^m)}{1-r} &= S,\\ \frac{ar^m(1 - r^n)}{1-r} &= T. \end{align}

In general there is not a neat formula to solve this system of equations, though some special cases do have formulas. One way to solve the system would first be to find $r$ such that $ \frac{1 - r^m}{r^m(1 - r^n)} = \frac ST, $ then use this value of $r$ in the original equations and solve for $a$: $ a = \frac{1-r}{1 - r^m} S $

There is software that can solve for $r$ in an equation like the one above.

For example, for the example you drew, with $m=2$ and $n=4$, \begin{align} \frac{a(1 - r^2)}{1-r} &= 80, \\ \frac{ar^2(1 - r^4)}{1-r} &= 20, \end{align} and we have a solution for $a \approx 54.9794,$ $r \approx 0.45509$, which gives you intervals of lengths approximately $54.9794, 25.0206, 11.3866, 5.1819, 2.3582$, and $1.0732$. (The last four add up to $19.9999$ due to rounding error.)

For $m=2$, $n=10$ we get $a \approx 55.2765,$ $r\approx 0.447271$. As you may notice, a relatively large change in $n$ is accommodated by a relatively small change in $r$; we end up packing a lot of very short intervals into a little space at the end.