If I understand the problem correctly, you have an array of m monotonically increasing, but unequally spaced, values. You want an array of n (> m) values than include the original m data points, but fill in the gaps between them.
I don't see a particularly nice solution -- even interpolation is tricky because you still want to keep the unequally spaced points.
Here's one possibility: take the m data points as m of the n points in your result, and distribute the remaining n - m points equally between the m - 1 spaces between the m data points. Given that you want to maintain the same density, equal distribution would do that fairly well. In that case, you need about k = (n-m)/(m-1) points between each pair of data points. Of course, that probably won't be an integer, so one solution would be to round that value down, leaving you with between 0 and m-1 leftover points to distribute. Here's my solution, distributing them to the biggest spaces between the data points:
m = 31;
n = 82;
x = sort(rand(m,1));
numbetween = floor((n-m)/(m-1));
k = 2 + numbetween*ones(m-1,1);
dx = diff(x);
[~,idx] = sort(dx,'descend');
numleftover = n - m - (m-1)*numbetween;
k(idx(1:numleftover)) = k(idx(1:numleftover)) + 1;
y = zeros(n,1);
i1 = 1;
for j = 1:(m-1)
i2 = i1 + k(j) - 1;
y(i1:i2) = linspace(x(j),x(j+1),k(j));
i1 = i2;
end
plot(x,0*x,'o',y,0.1+0*y,'x')
axis([0,1,-1,1])
(I'm using x for what you called S, and I just realized I have m and n reversed from what you had, sorry!)
