Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!gegeweb.42!gegeweb.eu!nntpfeed.proxad.net!proxad.net!feeder1-2.proxad.net!74.125.46.80.MISMATCH!postnews.google.com!news1.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.scnresearch.com!news.scnresearch.com.POSTED!not-for-mail
NNTP-Posting-Date: Mon, 31 Oct 2011 23:24:05 -0500
Newsgroups: comp.programming,comp.theory,sci.math,comp.graphics.algorithms
Date: Mon, 31 Oct 2011 21:24:03 -0700
From: William Elliot <marsh@rdrop.com>
Subject: Re: Worst Case Greedy Walk
In-Reply-To: <10a6051c-903f-4fd4-95e9-15e90dee066c@m19g2000yqh.googlegroups.com>
Message-ID: <20111031205413.D47073@agora.rdrop.com>
References: <10a6051c-903f-4fd4-95e9-15e90dee066c@m19g2000yqh.googlegroups.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII; format=flowed
Lines: 65
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 199.26.172.34
X-AuthenticatedUsername: NoAuthUser
X-Trace: sv3-gOjS81ZeKTK452w/tSoP2gKPEHH8eM19fIK2TkKk/jTzyFAPyYl0o3h7BLIzfJy9VEAFt4ONR0sluTV!yGtiHv8VTQCX6urCaaSshgC8u5Bz5U+LyTGy23GseBohsjLZRK6qLuUe5thBPZd7q+vX5thMgB16!5uU4vma2
X-Complaints-To: abuse@scnresearch.com
X-DMCA-Complaints-To: abuse@scnresearch.com
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3497
Xref: x330-a1.tempe.blueboxinc.net comp.programming:965 comp.theory:1287 comp.graphics.algorithms:549

On Mon, 31 Oct 2011, Andrew Tomazos wrote:

> I've reduced down a problem I am having in a project I am working on
> to the following...
>
> Given an integer n > 1
>
> Let S(n) be a set of n points in the euclidean unit square:
>
> ie { {x1, y1}, {x2, y2}, ..., {xn, yn} } all xi and yi are real
> numbers between 0 and 1 inclusive
>
No.  { a,b } is the set which contains only a and b.
(a,b) is an ordered pair (a first, b second) which is commonly
used for points of the real place writing (a,b) for the point
coordinates a on the x-axis and b on the y axis.

> such that the total distance of the path traveled by starting at the
> first point and moving directly to the nearest unvisited point (until
> they have all been visited) is maximized

That is ambiguous.  What if there is more than one "nearest" point?

For example:

{ (0,0), (a,a), (1,1), (0,1), (1,0) }	length 1 + 2.sqr 2

{ (0,0), (a,a), (0,1), (1,1), (1,0) }	length 2 + sqr 2

> S(2) is { {0,0}, {1,1} } total distance traveled is sqrt(2), we travel
> from {0,0} to {1,1} diagonally across the square.
>
> S(3) is { {0,0}, {0,1}, {1,0} } total distance travelled is 1 +
> sqrt(2), we travel up side of square from {0,0} to {0,1} for distance
> of 1, then across square to {1,1}
>
> S(4) is { {0,0}, {0,1}, {1,0}, {1,1} } total distance travelled is 3,
> we travel up from {0,0} to {0,1} then across to {1,1} then down to
> {1,0}
>
> S(5) (I suspect, but am not sure) is { {0.5,0.5}, {0,0}, {0,1}, {1,0},
> {1,1} } total distance travelled is 3 + sqrt(0.5)
>
> The goal would be to efficiently compute S(n) for arbitrary n
>
> Is there any way to calculate this set directly in some sort of closed
> form, or failing that can you think of a linear algorithm? polynomial?
> approximation?
>
> Does this problem reduce to some well-known problem? How?
>
I'm reminded of the equilibrium configurations of n electrons on a 
sphere.  Perhaps your problem is similar to the equilibrium 
configurations of n electrons confined to a square.

> What approach would you recommend?
>
> Thanks for your time.  Any thoughts appreciated.
>
Proper names and derivatives of proper names like "Euclidean"are spelled 
with an initial capital letter.

> Regards,
> Andrew.
>