Timeline for Shortest grid-graph paths with random diagonal shortcuts
Current License: CC BY-SA 3.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 18, 2014 at 0:44 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Fixed an old LaTeX typo in this posting. And expanded on LPP, as per comments.
|
| Nov 26, 2010 at 1:42 | history | edited | Omer | CC BY-SA 2.5 |
added 39 characters in body
|
| Nov 26, 2010 at 0:34 | comment | added | sleepless in beantown | @Omer, isn't the shortest length given by First Passage Percolation? | |
| Nov 14, 2010 at 19:45 | comment | added | Joseph O'Rourke | Thanks for the clarifications; I should have realized you meant steps. | |
| Nov 14, 2010 at 18:43 | comment | added | Omer | LPP = last passage percolation. Also, I assumed path length was in measures in steps and not Euclidean, but this does not change anything of the above. | |
| Nov 14, 2010 at 18:41 | history | edited | Omer | CC BY-SA 2.5 |
added 6 characters in body
|
| Nov 14, 2010 at 12:25 | comment | added | Joseph O'Rourke | LLP = Limited Path Percolation? | |
| Nov 14, 2010 at 12:25 | comment | added | Joseph O'Rourke | I actually use your nice observation that only {N,E,NE} steps are employed in the computations. Another way to phrase it is that a shortest path is both x-monotone and y-monotone. I think you meant that each diagonal reduces the distance by $2−\sqrt{2}$; but your point remains. Thanks for the remarks! | |
| Nov 14, 2010 at 2:23 | history | answered | Omer | CC BY-SA 2.5 |