Results 1 to 3 of 3

Math Help - separating points algorithm

  1. #1
    Newbie
    Joined
    Nov 2008
    Posts
    1

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Aug 2008
    Posts
    903
    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}]]
    Attached Thumbnails Attached Thumbnails separating points algorithm-lineprogram.jpg  
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Aug 2008
    Posts
    903
    I have some further thoughts about this. First I'll define the square ceiling function: s(n)=\lceil\lceil n \rceil\rceil to be the square closest to n but not less than n. So s(24)=25. Then I initially suspect the smallest number of lines meeting the above requirement for n points (not including the outer framing lines) is (\sqrt{s(n)}-1)^2. Note the figure below for n=8. It may or likely is not this simple but it's a start.
    Attached Thumbnails Attached Thumbnails separating points algorithm-minimumblocks.jpg  
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof about Separating Points, Vanishing, and Uniform Closure
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: July 13th 2010, 06:10 PM
  2. Separating these equations
    Posted in the Differential Equations Forum
    Replies: 6
    Last Post: November 27th 2009, 08:38 AM
  3. Separating constants
    Posted in the Algebra Forum
    Replies: 7
    Last Post: September 4th 2009, 05:31 AM
  4. Replies: 4
    Last Post: May 10th 2009, 10:29 AM
  5. Replies: 5
    Last Post: March 16th 2008, 04:19 PM

Search Tags


/mathhelpforum @mathhelpforum