Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Steve Thompson <thomps2048@yahoo.ca>
Newsgroups: comp.programming,comp.theory,sci.math,comp.graphics.algorithms
Subject: Re: Worst Case Greedy Walk
Date: Tue, 01 Nov 2011 20:56:54 -0400
Organization: A poorly organized news site.
Lines: 56
Message-ID: <AuXJNe.Y0A.vgVwo@invalid.invalid>
References: <10a6051c-903f-4fd4-95e9-15e90dee066c@m19g2000yqh.googlegroups.com> <4d432c49-dc17-4649-8c0f-06d8490cc96e@g27g2000pre.googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: mx04.eternal-september.org; posting-host="iyFSt7Y7BGsyUke8Uoi8DA"; logging-data="1756"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX183wHPPjop1LSu0SxLdu211"
User-Agent: KNqde/0.10.9
Cancel-Lock: sha1:r38pQJdjzrfcU76niRmfFUZmeZ8=
Xref: x330-a1.tempe.blueboxinc.net comp.programming:976 comp.theory:1297 comp.graphics.algorithms:558

On Tue, Nov 01, 2011 at 02:29:09PM -0700, Graham Cooper wrote:
> On Nov 1, 1:11 am, Andrew Tomazos <and...@tomazos.com> 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
> >
> > 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
> >
> > 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?
> >
> > What approach would you recommend?
> >
> > Thanks for your time.  Any thoughts appreciated.
> >
> > Regards,
> > Andrew.
> 
> a (square) spiral

Too obvious?  What about triangles?





Steve Thompson