Как лучше всего хранить диаграмму Вороного?
«Хранить диаграмму» нет смысла. 
Я бы хранил только координаты точек и при запросе делал поиск ближайшего соседа. Ведь весь смысл диаграммы Вороного - в разбиении на области, где ближайший сосед - одна из контрольных точек.Upd. Возможно, я ошибался и хранить диаграмму можно как binary tree, что даст более быстрый поиск ответа на принадлежность точки к области – обходом дерева. (или не даст?)
если нужно быстро узнавать ближайшую точку к заданной, то можно хранить диаграмму воронного в виде растровой карты.  
регулярная сетка, в каждой ячейке список ближайших точек. у большинства ячеек внутри полигонов диаграммы список будет из одного элемента, а на границах между полигонами - из нескольких.  
чем выше разрешение карты, тем больше попаданий и меньше вычислений на каждую точку.  при низком разрешении карты (если памяти мало), получится фильтр блума.