Combinatorial Geometry in MATLAB

From LiteratePrograms

Contents 1 Arrangement of hyperplanes 1.1 Minimal range of an arrangement of lines 1.1.1 Data generation 1.1.2 Crossings 1.1.3 Plot of the solution 1.1.4 All the code 1.1.5 Another option

Arrangement of hyperplanes

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

Here is a MATLAB implemented solution:

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))); 

Crossings

The crossings between all possible pairs of lines are computed. The crossing between lines and is defined by

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); 

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');

All the code

Image:Arrangement-min-lines.png

<<Arrangement_of_lines.m>>=
Data Generation
Crossings
Preprocess for plots
Plot arrangement

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