Say we wanted to create a latex table that had vertically centered text. Say furthermore that our table was very long and we wanted it to automatically span multiple pages.
Then we might imagine that the table would have a heading…
Followed by an ending at the end of the page…
Which would be continued at the start of the next page…
Such a table can be created using the snippet of code below. It uses the
array package for vertically centering the cell text and the
package for automatically breaking up the table across multiple pages.
Stack Exchange References:
A few months ago somebody asked the following question on AskReddit:
“If I wanted to randomly find someone in an amusement park, would my odds of finding them be greater if I stood still or roamed around?”
As usual, the comments were highly informative with various users running simulations to show that two people would generally find each other faster when both moved around. The question was lost in the detritus of my mind until a recent late-night conversation after a bioinformatics conference. The context in this conversation was different but the underlying question was the same.
“Are two proteins more likely to encounter each other when both are mobile or when one is attached to a cell membrance while the other is free to float around the interior of the cell?”
After bringing up the reddit post, I tried my best to explain why it would make sense that fixing the position of one person (or protein) would make it easier for the other to find it.
Alas, my memory had failed me and this conclusion was contrary to that suggested by the reddit comment simulations. What struck me, however, is that I couldn’t make a coherent case for why standing still is better, and wasn’t convinced by the other’s argument that moving around was better. Frustrated, I decided to make a little tool to perform a simulation of my own and to illustrate the phenomenon. So, without further ado, here we go.
One person (green circle) waits, while the other (red circle) searches. Both start at random positions at the start of each simulation.
Both people (green and red circles) move around. Both start at random positions at the start of each simulation.
To save you some time, I took the liberty of repeating these simulations for a variety of grid sizes and recorded the results.
|Grid Size||Both People||One Person|
It’s clear that the better strategy is for both people to move at random than to have one person wait while the other moves randomly.
Is this really a realistic scenario? How often do people just move around randomly? In most cases, when people are looking for something, they search in some methodic manner. The rest of this post will explore two fundamentally similar strategies and how they affect the search time.
The first strategy involves simply scanning the grid up and down, left to right.
The avoiding strategy involves keeping track of where the person has been, and at every point, visiting the least visited neighbor. If there is more than one least visited neighbor, pick one at random and continue.
A reddit user recently pointed out that a reasonable strategy might be for one person to just go to the center because there they would have a larger chance of being found by randomly moving person. An illustration of this appears below where the red person moves to the center and green person wanders around randomly.
To determine what the best course of action is when two people are separated somewhere, we need to do a pairwise comparison of the strategies on an 8x8 grid:
Generally, standing still is the best strategy if the other person is not moving around randomly. Even if they are, the best strategy appears to be to first go the center and stay put there. Moving around randomly is only optimal if the other person is doing an avoiding walk. Scanning and avoiding work well in general with one major caveat: if both people are scanning, it can lead to a situation where the two peole never meet, no matter how long they walk.
The avoiding strategy avoids (heh), this outcome by introducing a little bit of stochasticity into the searching process by picking a random position to go to when there are equally many least visited options available.
The best strategy is for people to choose a point at which they meet if they get lost. When both people go to the center, it takes a median of 3 moves and will never take more than four moves (on an 8x8 grid).
Often times, however, this doesn’t enter the conversation and an ad-hoc strategy must be selected. The second best option is for one person to stop moving and for the other to scan the search area looking for them. This also requires a certain amount of prior coordination to determine who will stop. If both people decide to stop, then it stands to reason that they’ll never find each other. Thus, when there is no agreed upon strategy, it appears that the best choice is to walk around avoiding places that you’ve already been and taking a random turn here or there.
Finally, if you’re really lazy it pays off to walk to the center and wait there. This will actually lead to a faster rendezvous when the other person is walking around randomly than walking around randomly yourself.
Read on for a look at the distributions of finding times and the application that made all of this possible.
Key Points from the Histograms:
A few people wondered how different the results would be on a 3D grid. It’s large-ish step to add 3D rendering to the current animations, but changing the code to use 3D dimensions wasn’t a huge deal. The results are in the table below.
The results a roughly analagous to those on the 2D grid. Naturally, it takes more moves for people to find each other in 3D, but the best strategy remains standing - avoiding, and moving in a random fashion is better than standing when the other person is also moving randomly. For those that are interested, the histograms below show the distribution of search lengths on a 3D grid.
Here’s an application that you can use to run your own simulation.
The source code for the application to run these simulations can be found on github.
Contouring is an important way for displying 3D data in 2D. At its core are iso-lines, along which values in the third-dimension have equal values, and iso-bands which are areas that encompasse values within some range (e.g. greater than 2 and less than 10). It is used for anything from topographical maps to show lines of equal elevation, weather maps to show regions of equal pressure to probability density plots to show regions with equal probability density. Calculating iso-lines and iso-bands is often done by interpolating values on a grid.
Pros: Simple. Adds contours to the edges of the data. True
||Pros: Options for specifying x- and y- values.||Pros: Interpolates the input data. Works with GeoJSON data structures.|
|Cons: Works only on gridded data. No option for specifying x- and y- values.||Cons: Works only on gridded data. Doesn't return true iso-bands. Requires a extra values to draw a border.||Cons: Interpolates the input data (can cause distortions). Works with GeoJSON data structures. Doesn't return actual iso-bands.|
MarchingSquares.js uses the eponymous
algorithm to calculate both iso-lines and iso-bands. Conrec.js uses a slightly
different algorithm and returns iso-lines, whereas Turf.js appears to use the
conrec algorithm to generate iso-lines. The examples above used the following
data set. The
breaks indicates where we want the iso-lines, and the iso-regions should
correspond to areas between adjacent
var breaks = [0, 4.5, 9, 13.5, 18]; var data = [[18, 13, 10, 9, 10, 13, 18], [13, 8, 5, 4, 5, 8, 13], [10, 5, 2, 1, 2, 5, 10], [9, 4, 1, 12, 1, 4, 9], [10, 5, 2, 1, 2, 5, 10], [13, 8, 5, 4, 5, 8, 13], [18, 13, 10, 9, 10, 13, 18], [18, 13, 10, 9, 10, 13, 18]];
MarchingSquares.js accurately returns is iso-bands and draws the plot as expected. Each path corresponds to a particular region. Thus hovering over the middle section also highlights the outer section which corresponds to the same values (13.5 - 18).
Conrec.js correctly outlines the regions, but the level returned for the second and third sections from the middle is the same although they should correspond to different iso-bands. To create the plot, it was also necessary to add some artifically high values along the outside boundaries so that iso-lines were drawn around the edges.
Turf.js interpolated the data onto another grid and drew iso-lines in the same manner as conrec.js. The automatic interpolation is listed in the table as both a pro and a con because it can be useful when the data is not already on a grid, but deleterious when it insists on using a uniform resolution on both the x and y scales and re-interpolating already gridded data (as in the example above).
Needless to say, of the three methods, MarchingSquares.js was the easiest and most aesthetically pleasing to me so I will likely use it in the future.
The code for all three of these examples can be found in a github repository here.
If you see any errors or omissions or know of a way to make the Turf.js example look more reasonable, please let me know on Twitter or by email.