Для хранения диаграммы Вороного можно использовать структуру данных, называемую полуразделенным деревом $англ.half-edgedatastructure$. Эта структура данных хорошо подходит для хранения сложных топологических структур, таких как диаграммы Вороного, потому что она позволяет эффективно реализовать операции навигации по граничным ребрам и вершинам.

В полуразделенном дереве каждое ребро разбивается на два направленных полуребра $half-edge$, каждое из которых содержит информацию о смежном ребре, вершине и полигоне. Таким образом, для каждого ребра в диаграмме Вороного находится два полуребра, одно из которых является "левым", а другое "правым".

Для нахождения ячейки $полигона$ в которую попала произвольная точка, можно использовать следующий алгоритм:

Начинаем с произвольной ячейки в диаграмме Вороного.Для каждого полуребра в данной ячейке проверяем, находится ли точка слева от этого полуребра.Если точка находится слева от всех полуребер в ячейке, то мы нашли ячейку, в которую попала точка. Если нет, то переходим к смежной ячейке, соединенной с текущей посредством полуребра.Повторяем шаги 2-3 до тех пор, пока не найдем ячейку, в которую попала точка.

Таким образом, используя полуразделенное дерево для хранения диаграммы Вороного и описанный алгоритм для поиска ячейки, в которую попала точка, можно эффективно работать с этой структурой данных.