Mapping the World with Hexagons

Hexagons are everywhere, from honeycombs to fly eyes to soap bubbles to the popular German board game, Settlers of Catan. And for good reason: hexagons are the most space-efficient regular polygon that can tile a plane. Or in bee terms, less wax — more honey.

But what do hexagons have to do with Helium?

At Helium, we’re building the world’s first decentralized machine network — a physical network of coverage for devices provided by gateways hosted throughout the world. Consequently, location is a core tenet of our network.

In addition to the need to represent a position in the world, our network also has some unique geospatial requirements: we need to encode precision and proximity. Precision (i.e. are we talking about a single point in space, or a larger, less precise area?) let’s us approximate range of coverage and anonymize gateway locations to some degree. Proximity allows us to reason which gateways are close to one another.

Uber’s H3: A Hexagonal Hierarchical Geospatial Indexing System

While there are plenty of coordinate systems out there, Uber’s H3 hexagonal grid system was a natural fit for our unique set of requirements.

Why do hexagons make for a good grid system? It turns out hexagons have some useful properties (as the bees among us already know). If you want to tile a plane with a regular polygon, you have just three options: equilateral triangles, squares, and hexagons. Of these three options, hexagons are the only shape which have the same distance to its neighbors. In comparison, squares have two different distances and triangles have three. This simple property vastly simplifies the math around calculating neighbor regions — a key function of our network.

Hexagonal grids are not without their weaknesses: for example squares subdivide perfectly from parent to children, whereas hexagons do not. This means there is a small degree of error when moving up or down in the hexagonal hierarchy. This tradeoff is acceptable in our network.

How we use H3 at Helium

We are currently using H3 for all aspects of geospatial representation within our network. Gateway and device locations are represented using small-resolution H3 indexes. H3’s resolution goes down to about 1m² which is plenty precise for representing location.

Additionally, we use the hierarchical property of H3 indexes to encode range of coverage. Our Proof-of-Coverage consensus module starts with a challenge group, which requires the calculation of nearby gateways within range of coverage. By using hierarchy to represent the precision of coverage, and H3’s k-ring feature, we’re able to efficiently generate the hexagons from which a challenge group can be selected. (For more details on our proof and its assumptions, see section 3.3.2 of the whitepaper)

On a more “superficial” level, H3 is a great tool for visualizing the state of our network. For example, our wallet uses H3 to visualize network coverage by aggregating and bucketing gateway locations into coarser grained hexagons. This is a very efficient way to represent large data sets of location at varying degrees of “zoom” while retaining a degree of privacy around the position of the underlying gateways.

Comparisons to Latitude & Longitude

When building a system so heavily-dependent on location, using latitude and longitude is a natural starting point. So why eschew this geographic coordinate system dating back to 190 BC?

The math for working with latitude/longitude coordinates is complicated and full of edge cases. Negative numbers represent latitudes north of the equator and longitudes west of the prime meridian. Additionally, floating point arithmetic is notoriously problematic.

On the list of minor annoyances, we can chalk up the fact that we need to store two pieces of information for each geospatial point. And conventions differ — sometimes latitude comes first, sometime longitude.

But what really pushed us away from latitude and longitude is that they’re inherently limited in the sense that they are only capable of representing a singular point in space. There is no natively encoded precision and proximity, which, as discussed, is critical to our network. H3 offers this.