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

  • 1
    $\begingroup$ What do you mean by "blend the divisions"? Perhaps you could draw a picture to explain? $\endgroup$ – Antonio Vargas Mar 6 '12 at 19:07
  • $\begingroup$ @Antonio: have added a picture and a bit more of an explanation. $\endgroup$ – PeteUK Mar 8 '12 at 18:42
  • $\begingroup$ Could you give some context on what problem you are trying to solve through this? I ask because it is a little unusual to do this sort of blending between divisions, and if we know more about what you are really trying to achieve, there may be a more natural solution for it. $\endgroup$ – Rahul Mar 9 '12 at 22:02
  • 1
    $\begingroup$ At first glance, this looks like it could be solved by a variant of monotone cubic interpolation, but I'd still like to hear your answer to my previous comment first. $\endgroup$ – Rahul Mar 9 '12 at 22:07
  • $\begingroup$ @Rahul: I'm in CAD and have a model from a scanner. It is discrete i.e. point cloud/triangulated mesh. The task is to uv parameterise the surface. The regions allow the user to specify the regions where they want more patches. In one region they might have 20 horizontal patches, in another they might have 5, so I'd like the change in patch size when transitioning from one region to another to not be "drastic". Hope this gives more context, if not, I can supply pictures of the actual application. $\endgroup$ – PeteUK Mar 9 '12 at 23:19

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$$


$$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.

  • $\begingroup$ $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. $\endgroup$ – PeteUK Mar 8 '12 at 18:43

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:


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$:


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


$c=20$, $m=6$, $n=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$:


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


$c=30$, $m=6$, $n=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.

  • $\begingroup$ I appreciate your answer. None of the pictures quite match the effect I'm trying to achieve so I'm not sure about polynomial interpolation. I reckon what I need is probably much simpler. Do you think I should delete and repost my question from fresh now I've added a bit more information as it seems to have gone very quiet now? $\endgroup$ – PeteUK Mar 9 '12 at 15:36
  • $\begingroup$ @PUK, whenever you edit your question it gets bumped to the front page, so it was back up there and visible 21 hours ago. I don't think it would be appropriate to repost it. Perhaps you should try another forum. reddit.com/r/math might be a good place to go. $\endgroup$ – Antonio Vargas Mar 9 '12 at 15:56
  • $\begingroup$ Asked on meta if I should repost and someone confirmed that's not a good idea. I didn't realise about the bumping. Thanks for your responses. $\endgroup$ – PeteUK Mar 9 '12 at 17:09
  • $\begingroup$ Were the number lines drawn by hand or is there a plotting tool for these? $\endgroup$ – Joseph Garvin Jan 27 '13 at 0:50
  • $\begingroup$ @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! $\endgroup$ – Antonio Vargas Jan 27 '13 at 1:06

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.