Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
separating points problem

Subject: separating points problem

From: Janik Janssens

Date: 26 Nov, 2008 14:21:02

Message: 1 of 4

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

Subject: separating points problem

From: David

Date: 26 Nov, 2008 17:29:01

Message: 2 of 4

"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?

Subject: separating points problem

From: Roger Stafford

Date: 27 Nov, 2008 05:19:02

Message: 3 of 4

"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

  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

Subject: separating points problem

From: Roger Stafford

Date: 27 Nov, 2008 20:43:01

Message: 4 of 4

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gglak6$ogh$1@fred.mathworks.com>...
> ........
> 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.)
> ..........

  In that n = 25 example I gave you yesterday, things are not quite as hopeless as I indicated. There are 2^24 = 1.6 x 10^7 ways of choosing subsets of horizontal lines. For each of these it takes only a single sweep through the 25 points along the x-axis direction to establish a minimum number of added vertical lines necessary to fulfill the required condition. This is far less than the 2.8 x 10^14 checks I mentioned previously, and could presumably be computed by Matlab in a reasonable amount of time.

  However, one need only increase the number of points to n = 50 to again encounter unreasonably long computations for getting exact minimums with such an algorithm.

Roger Stafford

Tags for this Thread

No tags are associated with this thread.

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us