Here's my gut instincts.

For the uniform interval case: take the two smallest y values and assign them to the endpoints. Assign the rest of the y values any way you want.

For the non-uniform interval case: You have two options: brute force search, or some sort of heuristic.

Option 1: brute force search will be $\displaystyle O(N!)$, where $\displaystyle N$ is the number of points. This is not good performance! The algorithm would like like this:

Option 2: heuristics. Here's one strategy: rank the intervals according to width. Rank the y values according to value. Perform a match-up of intervals to y-values in this order subject to the following constraints:Code:Largest_Area = - infinity; Best_Permutation = Y; For each permutation of the Y set: compute new_area = trapezoidal rule for non-uniform intervals; If new_area > Largest_Area Then Best_Permutation = Current_Permutation; Largest_Area = new_area; End If End For Output Largest_Area, Best_Permutation

1. I think you want to have all the trapezoids as close to being squares as possible. You might try minimizing the least squares formula that follows:

$\displaystyle \displaystyle{E=\sum_{j=2}^{N}\left((x_{j}-x_{j-1})-\frac{y_{j}+y_{j-1}}{2}\right)^{2}.}$

I don't know how you would do this, however. What you're changing is the permutation of the Y set.

This formula represents a measure of how far off from being square all the trapezoids are.

2. There must be continuity from one interval to the next. That is, only one y value may be chosen at the intersection of two intervals.

Example: X = {0,1,4,6,7}, Y={1,1,2,4,5}.

Ranking of x-intervals:

[1,4]

[4,6]

[0,1]

[6,7]

Ranking of y-values:

5

4

2

1

1

Matchup:

y = 5 and y = 4 correspond to [1,4]. Choose y = 4 and y = 2 to correspond with [4,6]. Choose y = 2 and y = 1 to correspond with [6,7]. Finally, choose y = 1 and y = 5 to correspond with [0,1]. That is, the Y set permutation is {1,5,4,2,1}.

Now this algorithm, as is, will not necessarily provide you with the absolute maximum sum. It will get close. As a matter of fact, the assignment Y = {1,4,5,2,1} gives a slightly higher area.

I think you generally want to assign larger y values to larger intervals. However, as I have already pointed out, there are further optimizations to be done. You might want to think about choosing the higher y values to be closer to the "x center of mass", which you could define as follows:

$\displaystyle \displaystyle{\overline{x}=\frac{\sum_{j=2}^{N}(x_ {j}-x_{j-1})\frac{x_{j}+x_{j-1}}{2}}{\sum_{j=2}^{N}(x_{j}-x_{j-1})}=\frac{1}{2}\frac{\sum_{j=2}^{N}(x_{j}^{2}-x_{j-1}^{2})}{\sum_{j=2}^{N}(x_{j}-x_{j-1})}.}$

Conclusion: the non-uniform case is a difficult problem. I'm not sure if I know of a sure-fire way to find the global max other than brute-force search. The algorithms I've outlined here will get you a good value, I think. But it's difficult. With lots of intervals, the problem can get very challenging indeed. You might consider evolutionary algorithms in order to avoid local maximums. Or an annealing algorithm. Here's a fantastic book that has loads of information on heuristics:How to Solve It: Modern Heuristics, by Michalewicz and Fogel. This book is simply a fun read. I'd highly recommend it.