Timeline for How to characterize a Self-avoiding path.
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 24, 2010 at 18:00 | vote | accept | Alexis Monnerot-Dumaine | ||
| Oct 13, 2010 at 8:51 | comment | added | Alexis Monnerot-Dumaine | I found a fractal pattern generated by the Fibonacci word, (by interpreting the sequence as a sequence of relative moves). The pattern looks clearly self-avoiding and I'd like to prove it. More generaly, I wonder how to characterise a loop, on a walk of relative moves, in a simple way. | |
| Oct 12, 2010 at 22:48 | comment | added | sleepless in beantown | @alexis-monnerot-dumaine, would you perhaps explain a little more about your motivation for this particular problem? Are you generating a fractal path or trying to walk along the edge of the mandelbrot set? What is the end-result that you are working on that this little piece would help with? (if you don't mind my asking...) | |
| Oct 11, 2010 at 8:13 | comment | added | Alexis Monnerot-Dumaine | Whow ! Lots of answers. I'm not sure I have the one I expect here. I need to read all this again. In the meantime, I edited again my question, because I am not precise enough. I hope this example makes things more clear. | |
| Oct 11, 2010 at 8:09 | history | edited | Alexis Monnerot-Dumaine | CC BY-SA 2.5 |
added 532 characters in body
|
| Oct 10, 2010 at 16:46 | answer | added | gowers | timeline score: 12 | |
| Oct 10, 2010 at 16:39 | history | edited | sleepless in beantown |
edited tags
|
|
| Oct 10, 2010 at 15:39 | answer | added | sleepless in beantown | timeline score: 10 | |
| Oct 10, 2010 at 11:27 | comment | added | gowers | How about first listing all the positions visited, then applying a fast sorting algorithm, and finally looking for two consecutive positions that are the same? I think that would take time Cnlogn, though at the cost of using quite a lot of memory. | |
| Oct 10, 2010 at 10:54 | comment | added | Qiaochu Yuan | @gowers: there are also quadratically many possible intersections, so it would be surprising to me if one could do significantly better. | |
| Oct 10, 2010 at 10:47 | comment | added | gowers | I think you should formulate the question as follows: what is the fastest algorithm for determining (in terms of the moves) whether a walk is self-intersecting? The obvious algorithm is just to look at each subinterval of the moves and see whether it is a loop. But there are quadratically many subintervals -- can we do better? | |
| Oct 10, 2010 at 9:57 | history | edited | Alexis Monnerot-Dumaine | CC BY-SA 2.5 |
deleted 11 characters in body
|
| Oct 10, 2010 at 8:08 | answer | added | Hugo van der Sanden | timeline score: 3 | |
| Oct 10, 2010 at 5:17 | history | edited | Bjørn Kjos-Hanssen |
edited tags
|
|
| Oct 9, 2010 at 8:43 | comment | added | Alexis Monnerot-Dumaine | Thanks. I have edited my question to precise the kind of rule I am looking for. It was not clear enough. Thanks. | |
| Oct 9, 2010 at 8:41 | history | edited | Alexis Monnerot-Dumaine | CC BY-SA 2.5 |
added 420 characters in body
|
| Oct 8, 2010 at 22:16 | comment | added | Qiaochu Yuan | The path is self-avoiding if and only if it's self-avoiding. I don't know what kind of rule you're looking for. Nothing that involves locally inspecting the sequence will do because self-avoidance is a global property, so there is some irreducible difficulty in this problem. | |
| Oct 8, 2010 at 22:04 | history | edited | Thierry Zell |
edited tags
|
|
| Oct 8, 2010 at 21:57 | comment | added | j.c. | Not sure exactly what you're asking, but you seem to be looking for information on self-avoiding walks: en.wikipedia.org/wiki/Self-avoiding_walk | |
| Oct 8, 2010 at 21:51 | history | asked | Alexis Monnerot-Dumaine | CC BY-SA 2.5 |