How do I create a pair of matrices approximating a convex hull of a set of points in 2-space?

I am trying to approximate the convex hull of payoffs for a 2x2 normal form game. The inputs would be the four points defining the payoffs at each of the four pure strategy outcomes, plus a factor k that would define the increments (and matrix sizes) of the approximating Row and Column player payoffs of the convex hull of payoffs. (So if k=10, the outputs would be a pair of 11x11 matrices UR and UC where UR has the convex hull payoffs for Row at 1/10 increments and UC has the convex hull of payoffs for Column at 10 point increments.)

My motivating problem is I'm trying to analyze an discretized approximation of a 2-playey bargaining problem that's constructed by creating the convex hull of payoffs for a 2x2 coordination game.

[Image Analyst]

I've never heard of convex hull in that context. Can you give some numerical example? And show why convhull() cannot be used to solve your problem.

[Peter Vanderschraaf]

I think what I'm trying to do is akin to the reverse of convhull(). If you begin with a set of points in 2-apsce then convhull() can help construct the polygon that bounds these points. I'm tring to start with four vertices that with convhull() would define a trapezoid and then tru to define the points at regular intervals inside this polygon. I'll try to0 provide a numerical example asap.

[Peter Vanderschraaf]

Here's a concrete version of the specific problem I'm trying to analyze. The bargaining problem is defined in part by the four vertex points (2,1), (4,10), (7,3) and (1,2). What I need to do is create a corresponding set of points that approximates the whole set of convex combinations of these four points. In other words, how do I approximate the values of the functions [0,1]x[0,1] into R2, knowing that

(0,0) maps to (2,1) = u(0,0) (0,1) maps to (4,10) = u(0,1) (1,0) maps to (7,3) = u(1,0) (1,1) maps to (1,2) = u(1,1)

It's easy to create matrices that approximate the unit square [0,1]x[0,1] into equal increments, but I'm having trouble constructing a program that would yield the output vector u(u,y) for (x,y) in [0,1]x[0,1] .

[José-Luis]

Here's what I would do. Express the point as the intersection of two lines going each from opposite segments of the unit square (make them orthogonal to those segments to make it simpler). Compute where those two lines intersect the unit square (really easy if they are orthogonal to said segments).

Express that as a fraction of segment length.

Project those four intersections to the new coordinates. Get the equation for those 2 new lines. The point you want would be the intersection of those two new lines.

[Peter Vanderschraaf]

Thank you for the speedy response Jose-Luis. I'm sorry for being dense but I'm having a little trouble interpreting your idea. If you have the time to respond again could you let me know how I would construct the specific map for the point (1/2,1,2) into the payoff set defined by those four vertex points (2,1), (4,10), (7,3) and (1,2)? I think if I can figure out how to do it for (1/2,1/2) (dead center of the unit square) then I should be able to figure it out more generally.

[Matt J]

@Peter

The mapping you describe is not unique, in general. Consider, for example, the special case of the mapping of the unit square into itself. One obvious candidate is

 u(x,y)=[x,y]

Another is

 u(x,y)=[y,x]

Yet another is the 90 rotation of the unit square about its center. There are infinite possibilities. You need more criteria.

[Matt J]

It is also possible that the mapping is nonlinear. For example, there is no linear/affine mapping that satisfies

(0,0) maps to (0,0) 
(0,1) maps to (0,1) 
(1,0) maps to (1,0) 
(1,1) maps to (2,2)

[José-Luis]

I assumed a linear mapping. If non-affine transforms come into play, funny things can start to happen.

Answer 1

[José-Luis]

Assuming linear mapping:

Not the most efficient thing out there, but it serves as a proof of concept. The important thing is that your vertices must be ordered either clockwise or counterclockwise:

   %You need to provide ordered vertices either clockwise or counterclockwise
  unit_square =  [0,0;...
                  0,1;...
                  1,1;...
                  1,0];
  mapped_poly = [2,1;...
                 7,3;...
                 4,10;...
                 1,2];

unit_square = [unit_square;unit_square(1,:)];
mapped_poly = [mapped_poly;mapped_poly(1,:)];

patch(unit_square(:,1),unit_square(:,2),'r','FaceAlpha',0.5);
hold on;
patch(mapped_poly(:,1),mapped_poly(:,2),'g','FaceAlpha',0.5);

point_to_project = rand(1,2);
x = point_to_project(1);
y = point_to_project(2);

plot(x,y,'ks');

bottom_position = mapped_poly(1,:) + x .* (mapped_poly(2,:) - mapped_poly(1,:));
right_position = mapped_poly(2,:) + y .* (mapped_poly(3,:) - mapped_poly(2,:));
top_position = mapped_poly(3,:) + (1 - x) .* (mapped_poly(4,:) - mapped_poly(3,:));
left_position = mapped_poly(4,:) + (1 - y) .* (mapped_poly(1,:) - mapped_poly(4,:));

%fit linear polynomial
p1 = polyfit([bottom_position(1) top_position(1)] ,[bottom_position(2) top_position(2)],1);
p2 = polyfit([left_position(1) right_position(1)] ,[left_position(2) right_position(2)],1);
%calculate intersection
x_intersect = fzero(@(x) polyval(p1-p2,x),3);
y_intersect = polyval(p1,x_intersect);

plot(x_intersect,y_intersect,'ks');

Answer 2

[Matt J]

If the mapping is a known linear/affine one, u=A*x+b, then you can do

   T=[A,b;[0 0 1]];

   [x,y]=ndgrid(linspace(0,1,10));
    pre=[x(:),y(:)].';
      pre(end+1,:)=1;

    u=T*pre;
     ux=u(1,:);
     uy=u(2,:);

   scatter(ux,uy)