Storing the (cell, edge) information

The number of edges in a cell is quite variable, as shown in figure 8. Most cells may be empty, and most of the remainder have only one edge. However, a few cells may have many edges. What data structure is appropriate then? In addition to the expandable array actually used, as described in section 5.2, there are several possibilities, as follows.

• Maintain a linked list of the edges in each cell. This allows the number of edges in a cell to grow without a specific limit. However, the pointers waste 50% of the space, the random allocation of elements may thrash virtual memory, and we can't randomly access the edges in a cell, but must follow the list in order.

• Append to a common (cell,edge) list, and then sort it to bring together the edges in each cell. This also allows a variable number of edges per cell, and also allows the edges in each cell to be accessed in random order. However this still wastes 50% of memory, storing the same cell numbers again and again in many different list elements. Also, many system sort routines are surprisingly bad, partly because they are written to be so general, so the user might need to implement this himself for efficiency.