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