15
$\begingroup$

The model:

Suppose that for each lattice point in $\mathbb Z^2$ we pick a random direction uniformly and independently. At time $t=0$ we start drawing rays starting from each lattice point in the chosen directions with unit velocity. The drawing of a ray will continue until it intersects another ray, at which point both rays stop.

In the end we are left with a graph $G$ (more like a union of segments, but let's pretend it's a graph), and I would like to understand it's properties.

Question:

This seems at first like it might share some properties with percolation in $\mathbb Z^2$, but I'm not so sure. I'd like to know how the connected components are distributed. For example, say we restrict to the lattice points inside the rectangle $[0,n]\times[0,m]$, and perform the process above (with the modification that if a ray hits the boundary rectangle it also stops). What is the expected number of connected components in $G$? (the boundary rectangle is not a part of $G$).

(There used to be a question here about cycles formed, but I removed it since it is more appropriate for motorcycle graphs mentioned in the answer below. For now, I want to focus on connected components. jc's answer seems to indicate that connected components will usually be small.)

$\endgroup$
6
  • $\begingroup$ Gjergji, I have a couple of questions. 1) Are the direction at lattice points independently chosen? And 2) when looking for cycles, do you see $G$ as a directed graph (according to the directions of rays) or not? Thank you! $\endgroup$ Aug 30, 2011 at 13:18
  • $\begingroup$ Yes, the directions are chosen independently. I'm not keeping track of the directions after the process ends, so the cycles aren't directed. $\endgroup$ Aug 30, 2011 at 13:42
  • 3
    $\begingroup$ Your process seems to be an extreme "anisotropic" version of the "lilypond model" mentioned in this answer of Louigi Addario-Berry mathoverflow.net/questions/40679/… $\endgroup$
    – j.c.
    Aug 30, 2011 at 16:51
  • 1
    $\begingroup$ Perhaps the probabilities could be explicitly computed in the special case of $n$ consecutive source points along the $x$-axis. For example, for $n=2$ the probability of obtaining a connected graph is $\frac{1}{4}$. $\endgroup$ Aug 31, 2011 at 5:09
  • $\begingroup$ May I ask: Is there a physical process your model is intended to capture? $\endgroup$ Aug 31, 2011 at 5:34

2 Answers 2

8
$\begingroup$

A variant of your model has been studied under the name of motorcycle graphs. Jeff Erickson has a very nice description here, from which I took this figure:
           JeffE
The emphasis in the computational geometry community has been: How quickly can the graph be computed, given starting points and initial directions. The interest has not been in the graphs per se (and so not in the properties in which you are interested), but rather their connection to the straight skeleton, a Voronoi-diagram-like construction involving unit-speed propagation of a polygon boundary. You might enjoy exploring David Eppstein's Java applet that permits you to interactively create motorcycle graphs.

$\endgroup$
4
  • 1
    $\begingroup$ Nice, thank you! One distinction is that in my model when a ray intersects another ray, both of them stop. $\endgroup$ Aug 30, 2011 at 15:37
  • $\begingroup$ @Gjergji: Ah, I did not understand that from your description (there are two possible referents for "that" in the phrase, "at which point that ray stops"!). So perhaps motorcycle graphs are not as close to your model as I thought... $\endgroup$ Aug 30, 2011 at 16:53
  • $\begingroup$ I don't understand the phrase "when a ray intersects another ray, both of them stop". Do you mean the ray that gets bumped into stops adding new stuff at that time, or is it supposed to stop at the common vertex? In the latter case, you would have to do some work to show you get anything in the limit, wouldn't you? $\endgroup$ Aug 30, 2011 at 18:08
  • $\begingroup$ @Anthony: the ray that gets bumped into stops expanding. The two rays don't necessarily meet at a common vertex. $\endgroup$ Aug 30, 2011 at 19:07
4
$\begingroup$

edit:

At Tom LaGatta's request, here are a few more very rough graphs relating to the number of components. For $n=3,\dots,15$, I ran just 10 instances of each (took about 15-20 minutes). Hopefully that's enough to give a little bit of the idea of the spread.

Here are the total number of components (with size>1) versus $n$. I noticed that it appeared parabolic, so I plotted it on a log-log scale with the function $n^2/3$ (the factor of 1/3 just happened to be close). Each data point corresponds to a different instance.

total number of components versus n

Here on semi-log scales are the distributions of numbers of components (with size>1) for the various grid sizes I considered. The different colors correspond to distributions observed in different instances. They look much better on semi-log as opposed to log-log, though that's fairly meaningless with not even a decade of data and small number effects.

grid of component size distributions

Code for this section (run with the functions in the notebook linked to below):

(* code to generate data, change parameters as needed *)
minn = 3;maxn = 15;numruns = 10;
data = Table[test = Flatten[makegrid[n, n], 1];Truncate[test], {j, numruns}, {n, minn, maxn}];
(* code to process and plot data *)
averagecomponents = Table[{n, Length[data[[i, n - minn + 1, 2]]]}, {n, minn, maxn}, {i, 
numruns}];
plot1 = ListLogLogPlot[averagecomponents, AxesLabel -> {"n", "total number of components"}];plot2 = LogLogPlot[x^2/3, {x, 1, maxn}];Show[plot1, plot2]
compdist = Table[Table[Tally[Table[Length[data[[j, n, 2, i]]], {i, averagecomponents[[n, j, 2]]}]], {j, numruns}], {n, maxn-minn+1}];
ListLogPlot[compdist[[12]], PlotStyle -> PointSize[Large]]
ListLogPlot[compdist[[13]], PlotStyle -> PointSize[Large]]
GraphicsGrid[Partition[Table[ListLogPlot[compdist[[j]], PlotStyle -> PointSize[Medium], PlotLabel -> "n=" <> ToString[j + minn - 1], AxesLabel -> {"size of component", "frequency"}], {j, maxn - minn + 1}], 3, 3, {1, 1}, {}]]
(* not shown: number of infinite rays *)
numinfinities = Table[{n, Count[data[[i, n - minn + 1, 1]], Infinity]}, {n, minn, maxn}, {i, numruns}]

original answer:

I wrote a bit of Mathematica code to try to simulate your process (link here). I only partially commented things, so let me know if you have trouble understanding how to use it. More on this after some pictures and graphs.

I apologize in advance, I don't have the time now to do a real systematic study or gather any real statistics on my computer. I'll have to leave it to you or other interested readers...

I didn't bother to add boundary conditions to cut off the rays leaving the grid. Below, components of size 1 are just rays that don't terminate.

5x5:

5x5 grid

8x8:

8x8 grid

15x15 grids:

(1) 15x15 grid #1

(2) 15x15 grid #2

Number of components of a given size for 15x15:

(1) 15x15 components 1

(2) 15x15 components 2

Stopping time distribution for 15x15 (excluding infinite rays, of which there are 6 in #1 and 7 in #2):

(1) 15x15 stopping times 1

(2) 15x15 stopping times 2

Note: I didn't see any cycles at all, but I had to check this by eye, since I didn't write a routine to extract the graph structure of the connected components. What I have now just records their size.

There is what looks like a cycle in the upper left quadrant of 15x15 #1, but you can easily convince yourself by comparing the lengths of the edges that the rays couldn't actually touch.


I used pretty much the most naïve algorithm I could think of:

  1. Generate a pseudorandom angle at each grid point, and thus get a set of lines.
  2. Find the intersection times of all pairs of lines. (Lines are naturally parametrized as $x(t)=x_0+t(\cos\theta,\sin\theta)$, where $x_0$ is the starting point and $\theta$ is the angle.)
  3. From this set of pairs, select pairs of rays that intersect in positive time rather than negative, and sort from smallest time to largest.
  4. Choose the intersection that occurs at the smallest time, mark the two rays involved as truncated, and record the connected component formed by this as a new one, and record the time of intersection as the "ending time" for the two rays.
  5. Check the intersection occurring at the next smallest time to see whether it's been preempted by existing rays (by comparing the intersection times with ending times), and if the intersection passes the test, mark these rays as truncated, and record the connected component and any new ending times as in 4.
  6. Repeat 5. until all intersections or all rays have been eliminated.

What are smarter ways of doing this?

Because of 2., the code runs rather slowly, probably $O(n^4)$ for an $n$ by $n$ grid ($n^2$ grid points, thus $(n^2)^2$ possible intersections). An instance at $n=15$ takes about 40 seconds on my machine to run.

$\endgroup$
7
  • 1
    $\begingroup$ Very nice, jc! Re "smarter ways of doing this": Yes, see the description by Jeff Erickson to which I linked. But all (known) smarter ways are complicated to implement. Your exponent of 4 could be reduced to ${\frac{17}{11}}^2 \approx 2.4$. $\endgroup$ Aug 31, 2011 at 11:44
  • $\begingroup$ jc, I would be very interested to know more details of the Number of Components graph. I suspect that this function exhibits power law decay. $\endgroup$ Aug 31, 2011 at 17:12
  • 1
    $\begingroup$ @Tom LaGatta, what kinds of details are you interested in? Perhaps you'd like a plot of the total number of components versus $n$? I'll try running a test though I won't be able to get to very large $n$. $\endgroup$
    – j.c.
    Aug 31, 2011 at 17:27
  • 1
    $\begingroup$ @Joseph O'Rourke, I notice that the source code for David Eppstein's applet is available. It's probably not hard to adapt the algorithm to Gjergji Zaimi's problem, though beyond my capabilities. $\endgroup$
    – j.c.
    Aug 31, 2011 at 17:41
  • $\begingroup$ Consider linked lists for each square surrounded by 4 points. Vectors which point into a square are added to the list for that square. In many (but not all) cases, those squares which have two or more vectors which point into the square will have at least one terminus inside that square, usually in time less than 1 and often in time less than 1.5. When you compute those segments for all squares by time delta, advance the clock for the remaining vectors and recompute which squares they hit. You may get the exponent below 3 this way. Gerhard "Ask Me About System Design" Paseman, 2011.08.31 $\endgroup$ Sep 1, 2011 at 3:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.