Thread: separating points algorithm

Hi,

I'm a belgian student in applied economics: commercial engineer. We have to write a paper including an algorithm for an optimization problem. Part of the exercise is to give and explain examples of software that already does what our algorithm does. Even if it is just a step in the program.

The separating points problem:
Consider a set of points in the plane, each point being determined by an x-coordinate and a y-coordinate. We assume, for reasons of convenience, that no two points have a common x-coordinate or a common y-coordinate. The problem that we face is to draw horizontal and/or vertical lines such that each pair of points is separated by some line. Thus, no cell in the subdivision of the plane induced by the lines, contains more than one point. The challenge is to use as few lines as possible to achieve this requirement.

Does anyone have an idea of which software incorporates this process? Or does anyone know if this can be done with some functions in Matlab, because we are not familiar with it.

Thx

Hi. My approach would be to first just draw a minimal excess of line: sort the x and y coordinates, take half the difference between each successive point, then draw lines at those points. That will segregate the points into blocks but will of course be an excess of lines. I don't have Matlab, but the Mathematica code below does that. Perhaps you can convert it to Matlab if you wish. Note I can remove the two red lines. Ok, now go through the line arrays and for each line, decide if that line can be removed. I'm not sure how to do that but you may wish to see if you can come up with some type of algorithm to do that.

Code:

nmax = 15; 
size = 10; 
pointlist = Table[{RandomReal[
      {-size, size}], RandomReal[
      {-size, size}]}, {nmax}]; 
plist = Point[pointlist]; 
xvals = Sort[(#1[[1]] & ) /@ pointlist]; 
yvals = Sort[(#1[[2]] & ) /@ pointlist]; 
xnew = Table[(xvals[[i]] + xvals[[i + 1]])/
     2, {i, 1, nmax - 1}]; 
ynew = Table[(yvals[[i]] + yvals[[i + 1]])/
     2, {i, 1, nmax - 1}]; 
xlines = (Line[{{#1, -size}, 
       {#1, size}}] & ) /@ xnew; 
ylines = (Line[{{-size, #1}, 
       {size, #1}}] & ) /@ ynew; 
Show[Graphics[{xlines, ylines, plist}]]

I have some further thoughts about this. First I'll define the square ceiling function: to be the square closest to n but not less than n. So . Then I initially suspect the smallest number of lines meeting the above requirement for n points (not including the outer framing lines) is . Note the figure below for n=8. It may or likely is not this simple but it's a start.