Identifying tiles in hyperbolic space?

[Coin]

"Identifying" tiles in hyperbolic space?

So I have a software project I've been working on on and off that involves the hyperbolic plane. There is something I am stuck on:

So let's say I have filled the hyperbolic plane with one of the tilings of regular n-gons. I now would like to "label" each individual tile with some sort of number or string which uniquely identifies it, in some pattern such that if I know a particular tile's "label" I can calculate the labels of the tiles which adjoin it.

So by analogy let's say this were the euclidean plane, and I had tiled it with squares:

In this case labeling is easy, my "label" is each square's coordinates (x,y), such that the square labeled (x,y) is bordered by (x-1,y),(x,y-1),(x+1,y) and (x,y+1).

When I am on the hyperbolic plane, it's less obvious to me how this would work and there doesn't seem to be a natural notion of integer "coordinates". I'm looking for a tiling that would look something like:

This is an ad hoc labeling (I made it in a graphics program, and I made one mistake...) for the "5,4" tiling, based around a sort of "polar" scheme where I tile one tile 1,1 and number "rings" out from that center with coordinates (r,t) with "r" being the ring number and "t" just being assigned around the circle. However this is just an example and doesn't actually help for my purposes unless I can look at the label (2,3) and somehow have a rule for deducing from the label that that tile is bordered by (1,1), (2,2), (3,9), (3,11) and (2,4).

Does anyone have any suggestions how to proceed? There seems to be a lot of information out there about these tilings in terms of what they mean in hyperbolic geometry, but less information about their discrete structure, and it's the discrete structure I'm interested in here.

Thanks.

 

[jim mcnamara]

Assuming your graphic represents your model, each element has 5 relatives. If you deem each n-gon a node then you have a 5-way (5-dimensional) tree. I don't see a lot of hope in designating them with two-dimensions. In a 5-way tree and with any uniquely indentified node, you know the position relative to neighbor nodes of your given node.

Or am I completely misunderstanding your question?

 

[Coin]

Assuming your graphic represents your model, each element has 5 relatives. If you deem each n-gon a node then you have a 5-way (5-dimensional) tree. I don't see a lot of hope in designating them with two-dimensions. In a 5-way tree and with any uniquely indentified node, you know the position relative to neighbor nodes of your given node.

Or am I completely misunderstanding your question?

Right. So if I look at things this way, then what I am looking for is some way to "name", or label with some other kind of mathematical object, each vertex, such that the vertex is uniquely identified. The reason I want to do this is that in my particular case I am exploring the graph using something like a random walk, and I need some way to tell, when I cross an edge from one vertex to the next, whether the vertex I have just come to is one that I have visited before.

The reason I am hoping this is possible is that the graphs corresponding to these tilings have a lot of structure that an arbitrary degree-5 regular graph doesn't. (And the two-dimensional "coordinates" aren't themselves important, I just used that as an example because that's the way I'd do it in Euclidean space.) I guess I'm just trying to figure out if this is a question that's been studied before.

(And to be clear the picture above is one of the tilings I'm looking at but I'm overall looking at a class of tilings such that for some combinations of (n,k) you have a tiling of regular n-gons where k of these n-gons meet at each polygon vertex. Using the graph terminology I guess you could say each (n,k)-tiling is an infinite planar regular graph of degree n whose dual graph is a regular planar graph of degree k? There are some more examples of these tilings in the link at the top of my initial post.)

 

[jim mcnamara]

Hmm. A quad-edge map in n-dimensions on a closed surface? I dunno.
Quad-edge data structures are used in three dimensional mappings. They provide what you seem to want. I do not have clue on generalizing.

The only reference I have is:
L J. Guibas & J Stolfi,
"Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams", ACM Transactions on Graphics, 4(2), 1985, 75-123

which is old. Sorry I can't provide something more substantive. Stolfi has libquad code here in C:

http://www.ic.unicamp.br/~stolfi/EXPORT/software/c/2000-05-04/libquad/