Optimize two dimensional search

Question

Assume we have two positive integer variables:

x = [1, W]
y = [1, H]

And the function:

F(x, y)

The task is to find the x and y that gives the maximum output value of the function (within the range).

A part of the function F is the known to be the area:

F(x, y) = (x * y) * T(x, y)

Now the other function T(x, y) has some interesting properties:

T(x + c, y) <= T(x, y)
T(x, y + c) <= T(x, y)

Where c is any positive integer greater than zero (indirect this makes T(x + c, y + d) true, where d has the same constraints as c).

Finding a working solution is easy by testing all possible x/y combinations, but the complexity is O(W*H).

Is there a way to exploit the properties described above to reduce the complexity?

Something like a binary search equivalence for 2D or such?

Walking the boundary in some way?

Do any of you bright minds have any interesting ideas or pointers?

An example of the output of T(x, y):

9 7 7 4 2
8 7 6 4 2
8 7 5 4 1
6 5 3 3 0
3 3 2 1 0

In this example, x = 4 and y = 3 gives the greatest value: 4 * 3 * T(4, 3) = 4 * 3 * 4 = 48.

Answer 1

Let R(x,y) be a function that satisfies

R(x,y) >= 1

and the following Lipschitz condition : for all (x,y) in [1,W]x[1,H],

• |R(x,y)-R(x+1,y)| <= 0.5 * 1/(W*H)^2

• |R(x,y+1)-R(x,y)| <= 0.5 * 1/(W*H)^2

Then it is a simple exercise in calculus to show that R(x,y)/(x*y) is a decreasing function of x and y.

Therefore, we can ask your problem with T(x,y) = R(x,y)/(x*y). We obtain the maximization problem of F(x,y) = R(x,y). As there is no fast way to obtain the maximum of a Lipschitz continuous function, your problem does not admit for a solution better than an exhaustive search.