Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: separating points problem
Date: Thu, 27 Nov 2008 20:43:01 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 12
Message-ID: <ggn0ol$bq3$1@fred.mathworks.com>
References: <ggjm0e$dme$1@fred.mathworks.com> <gglak6$ogh$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1227818581 12099 172.30.248.35 (27 Nov 2008 20:43:01 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Thu, 27 Nov 2008 20:43:01 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:503561


"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