T.R.
Reputation
Top tag
Next privilege 75 Rep.
Set bounties
 Sep 26 awarded Scholar Sep 26 accepted Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves Sep 25 revised Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves added 760 characters in body Sep 25 comment Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves It might have been better to call the turtle a robot. It simply executes a set of programmed moves over and over again until it covers the lattice. Sep 25 comment Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves @Joseph O'Rourke, Sorry, I should have been much clearer with the problem specification. The idea is that you have total information about the grid, control over where the turtle is placed, and the ability to program the turtle. The challenge is to minimize the length of the loop that governs its motions on the lattice while still insuring coverage under the constraint that no vertex can be re-visited. Sep 25 comment Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves @Sergei Ivanov, Please see the note I've added to the question. No instruction is allowed to direct the turtle off of the grid prior to coverage. Sep 25 revised Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves added 145 characters in body Sep 25 asked Covering a $d$-dimensional integer lattice by repeating a minimal set of deterministic moves Sep 24 comment Collisions between rooks taking random flights on an N by M chessboard @Joseph O'Rourke, thanks for recalculating the means for the $8x8$ and $4x4$ board! Sep 24 comment Collisions between rooks taking random flights on an N by M chessboard @Joseph O'Rourke, as a word of explanation for my original choice of [2], I was imagining that whatever was moving the rook wouldn't have global information about the rook's position on the board. To make an extremely tenuous connection, I thought of this question after reading a paper on how (GPS tracked) albatrosses' execute Lévy flights while engaging in foraging behavior: (pnas.org/content/early/2012/04/18/1121201109.abstract) Sep 24 comment Collisions between rooks taking random flights on an N by M chessboard @Joseph O'Rourke, Thanks for running these simulations! But could you clarify your statement that the rook can move off the board, and that this is counted as a move? And are you following the original suggestion in [2] that the rook's direction is randomly chosen? Sep 24 revised Collisions between rooks taking random flights on an N by M chessboard added 350 characters in body Sep 24 revised Collisions between rooks taking random flights on an N by M chessboard added 406 characters in body Sep 23 revised Collisions between rooks taking random flights on an N by M chessboard added 259 characters in body Sep 23 comment Collisions between rooks taking random flights on an N by M chessboard @Per Alexandersson, Absolutely you're right. But I posted the question here because I would be really interested if there are any techniques for tackling this problem in lieu of simulations. Sep 23 asked Collisions between rooks taking random flights on an N by M chessboard Sep 17 awarded Supporter Sep 17 awarded Editor Sep 17 awarded Student Sep 16 comment A discrete random walk that avoids previously visited vertices for an exponentially distributed time interval @Vincent Beffara, I agree with what you say. I'm certainly seeing long-term diffusive behavior for values of $p$ ranging from $p = 0.01$ to $0.99$. Also, and I didn't properly specify this, I'm allowing for an unblocking event, with non-zero probability in the same time interval that a site is blocked, so we are guaranteed reversals.