# Combinatorial Geometry in MATLAB

## 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

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

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


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


#### All the code

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

hijacker
hijacker
hijacker
hijacker