Re: Worst Case Greedy Walk

Path	csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!feeder2.ecngs.de!ecngs!feeder.ecngs.de!Xl.tags.giganews.com!border1.nntp.ams.giganews.com!nntp.giganews.com!local2.nntp.ams.giganews.com!nntp.bt.com!news.bt.com.POSTED!not-for-mail
NNTP-Posting-Date	Tue, 01 Nov 2011 02:27:57 -0500
From	"Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org>
Newsgroups	comp.programming, comp.theory, sci.math, comp.graphics.algorithms
References	<10a6051c-903f-4fd4-95e9-15e90dee066c@m19g2000yqh.googlegroups.com>
Subject	Re: Worst Case Greedy Walk
Date	Tue, 1 Nov 2011 07:21:05 -0000
X-Priority	3
X-MSMail-Priority	Normal
X-Newsreader	Microsoft Outlook Express 6.00.2900.5512
X-MimeOLE	Produced By Microsoft MimeOLE V6.00.2900.5512
X-RFC2646	Format=Flowed; Original
Message-ID	<E8qdnToqdLLgAjLTnZ2dnUVZ8iqdnZ2d@bt.com> (permalink)
Lines	18
X-Usenet-Provider	http://www.giganews.com
X-AuthenticatedUsername	NoAuthUser
X-Trace	sv3-eGESBf49472RknLQK4kClKv35yLQiGck2qO27ItrXMTiw5M+YRmNfyuM8E2xRjbesNliZHGf28ZjyjM!v1mt2b+rrXx0O1yNlaH7ZUjPWoArIVaRvqZHPh7yVR7RDKd4Wsgu7PFrRuZocXDPQAk7W3ewfA25
X-Complaints-To	abuse@btinternet.com
X-DMCA-Complaints-To	abuse@btinternet.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	1937
Xref	x330-a1.tempe.blueboxinc.net comp.programming:966 comp.theory:1288 comp.graphics.algorithms:550

Cross-posted to 4 groups.

Show key headers only | View raw

Andrew Tomazos wrote:

> 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

I suspect you may have missed something important out of the statement of the 
problem.  As it stands, I think you can get a path length arbitrarily close to 
(n-1) * sqrt(2) for even n, by clustering the points arbitrarily close to (0,0) 
and (1,1) such that each step of the traversal crosses the square.

If the positions of the points are fixed by some external constraint (which you 
haven't told us) then clearly the optimal algorithm will depend on the details 
of those constraints.

    -- chris

Back to comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-10-31 08:11 -0700
  Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-10-31 21:24 -0700
    Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:41 -0700
      Re: Worst Case Greedy Walk William Elliot <marsh@rdrop.com> - 2011-11-01 20:32 -0700
  Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-01 07:21 +0000
    Re: Worst Case Greedy Walk James Dow Allen <jdallen2000@yahoo.com> - 2011-11-01 00:45 -0700
      Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 13:02 -0700
        Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-02 09:57 +1300
          Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-03 10:55 +1300
            Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-03 09:39 +1000
              Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-07 17:09 +1300
                Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-08 04:04 +1000
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 09:54 +1300
                Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2011-11-13 11:50 -0800
                Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-14 06:58 +1000
                Re: Worst Case Greedy Walk seeWebInstead@rem.intarweb.org (Robert Maas, http://tinyurl.com/uh3t) - 2012-03-29 00:28 -0700
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 11:44 +1300
                Re: Worst Case Greedy Walk mike fee <m.fee@irl.nospam.cri.nz> - 2011-11-08 14:28 +1300
    Re: Worst Case Greedy Walk Andrew Tomazos <andrew@tomazos.com> - 2011-11-01 12:46 -0700
      Re: Worst Case Greedy Walk "Chris Uppal" <chris.uppal@metagnostic.REMOVE-THIS.org> - 2011-11-02 08:16 +0000
        Re: Worst Case Greedy Walk Patricia Shanahan <pats@acm.org> - 2011-11-02 05:27 -0700
  Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 14:29 -0700
    Re: Worst Case Greedy Walk Graham Cooper <grahamcooper7@gmail.com> - 2011-11-01 15:30 -0700
    Re: Worst Case Greedy Walk Steve Thompson <thomps2048@yahoo.ca> - 2011-11-01 20:56 -0400
  Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 01:55 -0500
    Re: Worst Case Greedy Walk quasi <quasi@null.set> - 2011-11-02 18:24 -0500
  Re: Worst Case Greedy Walk "INFINITY POWER" <infinity@limited.com> - 2011-11-02 17:49 +1000

csiph-web