MathGroup Archive 2007

[Date Index] [Thread Index] [Author Index]

Search the Archive

"Elastic string" (type of traveling-salesman) paradigm for sampling discrete data sets

  • To: mathgroup at smc.vnet.net
  • Subject: [mg78198] "Elastic string" (type of traveling-salesman) paradigm for sampling discrete data sets
  • From: Curtis Osterhoudt <cfo at lanl.gov>
  • Date: Mon, 25 Jun 2007 07:08:17 -0400 (EDT)
  • Organization: LANL
  • References: <200706131143.HAA07211@smc.vnet.net> <200706210953.FAA27469@smc.vnet.net>
  • Reply-to: cfo at lanl.gov

Dear MathGroup, 

   This is a question which might open up far more cans of worms than I'd 
like, but it has got me thinking, and I can always use help with that. 
Forgive the length of the post!

   I'm writing some code (in Mathematica) to calculate the fractal 
dimension(s) of nominally 1D datasets; an example would be discretely-sampled 
{time, single_coordinate} sets. This brings me to my first question: other 
than the simple approach described in "The Fractal Dimension of the Blues" 
notebook[1], are there relatively accessible Mathematica codes out there 
already?

Regardless of the answer to the first question, I've another. One way in which 
to sample a discrete data set (or even a continuous function) is to imagine 
an elastic string stretched between the first and last data points. Then, 
specify how many (straight) sections the string is allowed to be deformed in. 
For just one section, the string just goes straight from the first to the 
last point. For two sections, the string goes from the first point, to 
somewhere on the dataset, and then from there to the last point. 
The "elastic" part of the wording is to imply that the string's length is 
required to be the shortest possible, passing through the first, last, and 
any intermediate sampling points. (The possibility of allowing for 
interpolation between data points causes massive problems---at least in my 
mind---as to how sample things correctly, so I'll leave that concept aside 
for the moment.) This is a sort of "free" traveling-salesman problem, with 
the salesman picking and choosing a set number of points to visit between the 
first and last.
   I'm imagining a rather icky optimization problem (especially for large 
datasets), and wonder if anyone has some hints or suggestions as to how to 
make relatively quick code. I'm totally open to the spewing-forth of ideas, 
whether or not they're very carefully considered.
As a first guess at the algorithm, I can fix the first and last points of the 
string, then run a "bead" affixed to the string along each of the remaining 
points, and see which one ends up minimizing the string length (obviously a 
point between the first and last points in both dimensions, _if_ the sampled 
data allows for such a thing). As more points are allowed to be sampled, it's 
almost certain that previously-affixed points will have to become unglued, 
and attach themselves elsewhere.

    Any suggestions? This may be a common problem with some famous and 
efficient solutions, but I'm not familiar with them. Even some good websites 
or journal article suggestions would be very welcome.

           Best wishes, 
                 Curtis O.




[1] Available as  
http://calcand.math.uiuc.edu/courseware/Old%20Stuff/Pictures_and_Math_Fun/Fowler's%20Neat%20Graphics/13fracBluWRI.nb
-- 
==========================================================
Curtis Osterhoudt
cfo at remove_this.lanl.and_this.gov
PGP Key ID: 0x4DCA2A10
Please avoid sending me Word or PowerPoint attachments
See http://www.gnu.org/philosophy/no-word-attachments.html
==========================================================


  • Prev by Date: Wish for undo feature applied to Format -> Style
  • Next by Date: Re: save as pdf in version 6
  • Previous by thread: Re: OpenSSH mathlink remote kernel connection problem.
  • Next by thread: Re: "Elastic string" (type of traveling-salesman) paradigm for sampling