Re: Worst Case Greedy Walk

Date	2011-11-02 05:27 -0700
From	Patricia Shanahan <pats@acm.org>
Newsgroups	comp.programming, comp.theory, sci.math, comp.graphics.algorithms
Subject	Re: Worst Case Greedy Walk
References	<10a6051c-903f-4fd4-95e9-15e90dee066c@m19g2000yqh.googlegroups.com> <E8qdnToqdLLgAjLTnZ2dnUVZ8iqdnZ2d@bt.com> <371f8ed6-edb5-469f-aeae-27642294d93a@s9g2000yqi.googlegroups.com> <yNydnRmdBsWNYS3TnZ2dnUVZ8iidnZ2d@bt.com>
Message-ID	<gfqdnUBP5-DMqizTnZ2dnUVZ_qednZ2d@earthlink.com> (permalink)

Cross-posted to 4 groups.

Show all headers | View raw

On 11/2/2011 1:16 AM, Chris Uppal wrote:
...
> On the other hand, it might be worth thinking of it the other way around.
> Start by packing a "long" path into the unit square, and then asking how /few/
> points you can distribute along it such that neareast-unvisited-neghbour
> constraint forces traversal of that path.  Makes me wonder if a Hilbert curve,
> or other connected space-filling curve, might be fruitful (although I have no
> communicable reason to expect a space-filling curve to be better than just a
> zig-zag pattern, or similar).

I was also thinking along the line of packing a path. The problem is
that there are several ways to do it, including zig-zag and spiral.

Each general approach leads to a family of solutions with parameters
that select a specific solution within the family. The permitted and
optimal parameter settings within a solution family depend on the number
of points. Picking that solution within family is, in general, an
integer optimization problem.

My best suggestion for tackling this problem is to start with some
simple solution families, and determine the best solution in each
family. It may be possible to show that one family is always better than
another e.g. if the number of points is greater than N.

I don't see an obvious way to prove that a solution is overall optimal,
because there may be another family that has not yet been proposed that
contains a better solution.

Patricia

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