### Optimizing spacing of mesh containing a given set of points

Posted:

**Sat Jan 15, 2011 9:27 pm UTC**I tried to summarize the this as best as possible in the title. I am writing an initial value problem solver in the most general way possible. I start with an arbitrary number of initial values at arbitrary locations (inside a boundary.) The first part of my program creates a mesh/grid (I am not sure which is the correct nuance), with N points total, that contains all the initial values. My goal is to optimize the mesh such that the spacing is as uniform as possible. My solver seems to work half decently (it needs some more obscure debugging that is not relevant here.)

I am starting with one dimension. I intend to generalize the algorithm to an arbitrary number of dimensions once I get it working consistently. I am writing my code in fortran, but feel free to reply with pseudocode or the language of your choice.

Allow me to elaborate with an example:

Say I am working on a closed interval [1,10]

xmin=1

xmax=10

Say I have 3 initial points: xmin, 5 and xmax

num_ivc=3

known(num_ivc)=[xmin,5,xmax] //my arrays start at 1. Assume "known" always starts sorted

I store my mesh/grid points in an array called coord. Say I want 10 points total in my mesh/grid.

N=10

coord(10)

Remember, all this is arbitrary--except the variable names of course.

The algorithm should set coord to {1,2,3,4,5,6,7,8,9,10}

Now for a less trivial example:

num_ivc=3

known(num_ivc)=[xmin,5.5,xmax]

or just

num_ivc=1

known(num_ivc)=[5.5]

Now, would you have 5 evenly spaced points on the interval [1, 5.5] and 5 evenly spaced points on the interval (5.5, 10]? But there is more space between 1 and 5.5 than between 5.5 and 10. So would you have 6 points on [1, 5.5] followed by 4 on (5.5 to 10]. The key is to minimize the difference in spacing.

I have been working on this for 2 days straight and I can assure you it is a lot trickier than it sounds. I have written code that

only works if N is large

only works if N is small

only works if it the known points are close together

only works if it the known points are far apart

only works if at least one of the known points is near a boundary

only works if none of the known points are near a boundary

So as you can see, I have coded the gamut of almost-solutions.

I thank all those who attempt this dastardly problem.

Good luck!

I am starting with one dimension. I intend to generalize the algorithm to an arbitrary number of dimensions once I get it working consistently. I am writing my code in fortran, but feel free to reply with pseudocode or the language of your choice.

Allow me to elaborate with an example:

Say I am working on a closed interval [1,10]

xmin=1

xmax=10

Say I have 3 initial points: xmin, 5 and xmax

num_ivc=3

known(num_ivc)=[xmin,5,xmax] //my arrays start at 1. Assume "known" always starts sorted

I store my mesh/grid points in an array called coord. Say I want 10 points total in my mesh/grid.

N=10

coord(10)

Remember, all this is arbitrary--except the variable names of course.

The algorithm should set coord to {1,2,3,4,5,6,7,8,9,10}

Now for a less trivial example:

num_ivc=3

known(num_ivc)=[xmin,5.5,xmax]

or just

num_ivc=1

known(num_ivc)=[5.5]

Now, would you have 5 evenly spaced points on the interval [1, 5.5] and 5 evenly spaced points on the interval (5.5, 10]? But there is more space between 1 and 5.5 than between 5.5 and 10. So would you have 6 points on [1, 5.5] followed by 4 on (5.5 to 10]. The key is to minimize the difference in spacing.

I have been working on this for 2 days straight and I can assure you it is a lot trickier than it sounds. I have written code that

only works if N is large

only works if N is small

only works if it the known points are close together

only works if it the known points are far apart

only works if at least one of the known points is near a boundary

only works if none of the known points are near a boundary

So as you can see, I have coded the gamut of almost-solutions.

I thank all those who attempt this dastardly problem.

Good luck!