Hacker News Reader

Comment by jordigh | Hacker News Reader

Tangentially related, I have heard of modelling forest fires with cellular automata.

http://en.wikipedia.org/wiki/Forest-fire_model

The grid is usually rectangular, and I've always found this a bit odd: hexagons represent 2-d sphere packing, so they always seemed more natural to me. I once asked researchers in the field about this, around 2006, and they responded that rectangular grids serve just as well. I just found this paper from 2007 where apparently hexagonal grids fare better:

http://www.sciencedirect.com/science/article/pii/S0307904X06...

This makes me wonder, for realistic models that are meant to model a notion of neighbour cells, why aren't we always using hexagonal grids in 2d or higher-dimensional analogues? With rectangular grids, you're always faced with the choice of defining whether touching on edges and corners count as neighbours or not, which seems like an unnatural choice. Why, then, does this not seem to matter in the end?

View on HN

If rotational symmetry is important to the dynamics, you're likely to do much better on coarse grids with a hex layout, because it has a finer rotational symmetry.

Of course, with a small-enough grid rotational symmetry should be restored (or you've chosen a poor discretization!). One might rephrase your statement as: the lattice artifacts / discretization errors vanish faster on a hex grid. Could be.

When I worked on fire-spreading models [0] the grids we used were square. I would wager that this is because it makes thinking significantly easier. In my current field[1], square lattices are chosen because of the underlying supercomputing architecture. The communication mesh in tera- and petascale computers tend to be rectangular [2]. At these scales, having a nice rectangular layout of the local subvolumes simplifies communication algorithms and can provide a dramatic speedup---in this case having fewer neighbors is better.

[0]: In high school I implemented the fact that fires burn faster uphill while working for David Keyes on http://www.cs.cmu.edu/~caliente/

[1]: Lattice QCD codes use a (4D spacetime) rectangular lattice https://usqcd-software.github.io/

[2]: The BlueGene/Q, for example, is a 5-dimensional rectangular torus.

Square grids are more intuitive: they map to our standard cardinal and ordinal directions. As long as you treat the ordinal neighbours (the corners) as being sqrt(2) away from the center (as oppposed to 1 away from the center like the cardinal neighbours, or all of the hexagonal neighbours) then you don't get spatial distortions.

I can provide an intuitive thought picture answer, that if you're doing something that boils down to numerical integration under a curve, a pile of hexagons or other polygons will win over a simple raster array of square pixels at a similar quantity of polygons, but when implemented, if its computationally cheaper to run the rectangular raster array at 10, 100, maybe 1000 times the resolution of the hexagon implementation, then the raster will always win at the overall systemic level at the numerical integration game. Not implying forest fires are simple numerical integration games, but they are similar-ish in trying to discrete-ize a non-discrete analog problem.

If you were talking about EE DSP stuff, you'd call it quantization noise. Theoretically a floating point A/D converter would be nice / interesting if such a thing existed, but in practice you minimizing that noise source by using more fixed bits per sample.

As far as I know the reason why square lattices are preferred over hex lattices is that they can easily generalized to 3D, ... . If you invest lots of time thinking about good, say, FEM or Finite Volume algorithms, you want to have results that can easily generalized afterwards.

Actually there is a simple 3D analog of the hexagonal grid, which occurs in crystal structures. Somewhat interestingly there are two variants, known in crystallography as Face-Centred Cubic and Hexagonal Close Packing. http://en.m.wikipedia.org/wiki/Close-packing_of_equal_sphere...

In higher dimensions there are applications to broadband coding (you want the densest possible constellation).

http://mathworld.wolfram.com/HyperspherePacking.html

Though perhaps more relevant to FEM is the tetrahedral mesh...

Both types are important. The math is indeed more complicated for square meshes, but you can use the fact that the basis functions (is this the proper English translation of the German "Basisfunktionen"?) on square elements have more degrees of freedom to sometimes get better approximations.

Disclosure: I heard some advanced lectures about FEM intended for students who intended to write a diploma thesis about this topic.

As a part of my university coursework I modeled forest fires with a grid but mine had varying densities of forests and each tree affected an area around it, not just adjacent cells. It's a really interesting thing to try and model if you get a chance, because tiny adjustments can make a world of difference.

Just a conjecture, but, it may not always be possible/straightforward to map a set of CA rules meant for a rectangular grid to a hex grid.

Reply on news.ycombinator.com