MathGroup Archive 2007

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

Search the Archive

Re: "Elastic string" (type of traveling-salesman) paradigm for sampling



Hi Curtis,

if you can solve a problem in different ways, you should pick the 

simplest one. Further, a good measure of dimension should not depend 

(strongly) on how you pick the points. Therefore, I would replace 

separated points by a continuous line by linear interpolation (assuming 

the point are ordered). Then you can simple put your measure-stick along 

this line.

hope this helps, Daniel



Curtis Osterhoudt wrote:

> 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




  • Prev by Date: Re: A Note of Thanks
  • Next by Date: RE: Plot in a Do loop does nothing
  • Previous by thread: "Elastic string" (type of traveling-salesman) paradigm for sampling discrete data sets
  • Next by thread: Integrate question