From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: separating points problem
Date: Thu, 27 Nov 2008 05:19:02 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 22
Message-ID: <gglak6$ogh$>
References: <ggjm0e$dme$>
Reply-To: <HIDDEN>
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: 1227763142 25105 (27 Nov 2008 05:19:02 GMT)
NNTP-Posting-Date: Thu, 27 Nov 2008 05:19:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: comp.soft-sys.matlab:503453

"Janik Janssens" <> wrote in message <ggjm0e$dme$>...
> Hi, 
> I'm a belgian student in applied economics: commercial engineer. We have to write a paper and 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 what software solves the problem? Or does anyone know if this can be done with some functions in Matlab, because we are not familiar with it.
> Thx

  Janik, there is no loss of generality in supposing that your n x-values and y-values occur at equally spaced intervals on the two axes, and that in turn these can be represented by a single n by n matrix of n 1's with the remainder being all 0's and in which each row and each column possesses just a single 1.  In those terms it is a strictly combinatorial problem that, in theory, Matlab could handle.

  However the difficult part of your task is discovering an appropriate algorithm.  Once devised, it should be possible to translate any such algorithm into Matlab code.  My impression is that it will in fact be exceedingly difficult to invent an algorithm that is guaranteed to always find the desired minimum precisely if large numbers of points are to be dealt with.  The methods that first come to mind would require hopelessly large numbers of steps with large numbers of points in your set.  For example, for only 25 points there exist something like 2.8 x 10^14 different "cell" subdivisions to be checked (if all were to be blindly tested.)

  A heuristic procedure that only seeks approximate minimum values can conceivably handle the problem of large point sets but my guess is that such an algorithm would nevertheless require a very extensive software program to realize if reasonably good results are to be obtained.  For that, not only would you need to have a very inspired idea as to the needed heuristic algorithm, but developing the necessary implementation in Matlab, or in fact in any programming language, would require a rather detailed knowledge of that language.

  I would be very surprised if there were any simple functions in Matlab, or in any other language I have ever heard of, that could easily achieve what you are seeking.

Roger Stafford