Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: separating points problem
Date: Wed, 26 Nov 2008 17:29:01 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 13
Message-ID: <ggk10t$o7d$1@fred.mathworks.com>
References: <ggjm0e$dme$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1227720541 24813 172.30.248.38 (26 Nov 2008 17:29:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Wed, 26 Nov 2008 17:29:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 791003
Xref: news.mathworks.com comp.soft-sys.matlab:503356

"Janik Janssens" <airjanik@hotmail.com> wrote in message <ggjm0e$dme$1@fred.mathworks.com>...
> 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

interesting problem.  i wonder if it is related to delaunay triangulation or a voronoi diagram.  would bisecting the sides of the delaunay triangles give you the appropriate sets of lines, then you could reduce the set by removing lines with no points between them?