"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
==========================================================
- References:
- OpenSSH mathlink remote kernel connection problem.
- From: anguzman@ing.uchile.cl
- Re: OpenSSH mathlink remote kernel connection problem.
- From: Steve Wilson <stevew@wolfram.com>
- OpenSSH mathlink remote kernel connection problem.