Combinatorial Geometry in MATLAB

From LiteratePrograms
Jump to: navigation, search

Contents

[edit] Arrangement of hyperplanes

[edit] Minimal range of an arrangement of lines

Following a question on the MATLAB newsgroup:

An interesting problem came up recently. 
It probably has a simple solution that I'm 
coming up blank on. 

Given a pair of (real) vectors, a and b, each of length n.

Find X (a real scalar) that minimizes the expression

Y = \max(a+X \, b) - \min(a+X \, b)

Here is a MATLAB implemented solution:

[edit] Data generation

Here the data are randomly generated, and the function to minimize is defined:

f_crit - the scalar version of the criteria
F_crit - the vectorized version of the criteria


<<Data Generation>>=
n = 5; 
a = rand(n,1); 
b = rand(n,1); 
f_crit = @(X) max(a+X*b) - min(a+X*b); 
F_crit = @(X) max(repmat(a,1,length(X))+repmat(X',length(a), 1).*repmat(b,1,length(X))) - ...
              min(repmat(a,1,length(X))+ repmat(X',length(a),1).*repmat(b,1,length(X))); 

[edit] Crossings

The crossings between all possible pairs of lines are computed. The crossing between lines y=a+b\,x and y=A+B\,x is defined by

x(a,b;A,B)=-\,\frac{a-A}{b-B}

Note how the upper triangular elements of the matrix are selected, they are sorted only for the pollowing plot.

<<Crossings>>=
crossings = -(repmat(a,1,n)-repmat(a',n,1))./(repmat(b,1,n)-repmat(b',n,1)); 
triu_id   = cumsum(eye(n),2)-eye(n); 
crossings = sort(crossings(logical(triu_id))); 
crossingy = F_crit(crossings)'; 
[Y,idX]   = min(crossingy); 
X         = crossings(idX); 

[edit] Plot of the solution

To plot the solution, some computations have to be made first:

<<Preprocess for plots>>=
domainx = [min(crossings), max(crossings)]; 
domainy = [a+b*domainx(1), a+b*domainx(2)]; 
miax = [min(domainy(:)), max(domainy(:))]'; 
allx = [repmat(crossings,1,2), repmat(nan,length(crossings),1)]'; 
ally = repmat([miax; NaN],1,length(crossings)); 

They the solution is plotted in two stages:

  • the arrangement of lines and their corssings
  • the criteria, on which the crossing are plotted, and the overall minimum
<<Plot arrangement>>=
figure('color', [1 1 1]); 
a1=subplot(2,1,1); 
plot(domainx, domainy, 'linewidth',2); 
hold on 
plot(allx(:),ally(:),':k'); 
hold off 
title('All lines'); 
a2=subplot(2,1,2); 
plot(crossings,crossingy,'-', 'linewidth',2); 
hold on 
plot(X, Y, 'or', 'Markerfacecolor', [1 0 0]); 
plot(crossings,crossingy,'.k'); 
hold off 
text(X,Y,sprintf('  X=%5.2f, Y=%5.2f', X, Y), 'rotation', 90) 
title('Minimum'); 
linkaxes([a1,a2],'x');

[edit] All the code

Arrangement-min-lines.png

<<Arrangement_of_lines.m>>=

Data Generation

Crossings

Preprocess for plots

Plot arrangement

[edit] Another option

It is possible to use the fsolve function directly.

At first the function to optimize has to be entered:

<<mimafun>>=
function y=mimafun(x,a,b) 
%a,b = columns 
V=a+b*x; 
V(:,2)=-V; 
y=sum(max(V));

And then directly used:

<<fsolve direct use>>=
[X, Y]=fsolve(@(x) mimafun(x,a,b),0)
Download code
hijacker
hijacker
hijacker
hijacker