It is maybe worth noting that triangles are 2D simplices, so for a non-flat mesh, triangles are a simpler solution. Hexagons won't always be flat. There's a literature of progressive mesh transmission that does fun things with mesh topology. Not sure if it's still a live topic but I remember a paper with nice illustrations from 2001:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.19.5...