Прямоугольное разбиение плоскости по опорным точкам

[Mysterious Light]

Имеется конечное (точнее, счётное, но периодическое, вроде узлов кристаллической решетки) множество точек $S$ на плоскости.
Диаграмма Вороного позволяет построить разбиение на многоугольники, каждый из которых состоит из точек, которые более приближены к своей опорной точке, чем к любой другой из $S$. Диаграмма однозначна.
Нужно построить нечто аналогичное, но для прямоугольников с паралельными осям сторонами. Опорная точка внутри своего прямоугольника, как можно дальше от границы. Поскольку формального описания не привожу, подобное разбиение не однозначно.

Прошу подсказать наиболее простой алгоритм этой неконкретно сформулированной задачи.

[Mysterious Light]

Задача не разрешена, но потеряла актуальность (остановился на диаграммах Вороного, не столь удобных, но понятных и уже реализованных в стандартных библиотеках)

Единственное, до чего я дошел, это то, что можно считать подходящее прямоугольное разбиение таким, что все углы прямоугольников находятся на середине отрезков, соединяющих соседей. Основным видом стыков является Т-образный стык, который возможен в 4 ориентациях. Стало быть, все варианты разбиений нумеруются и перебираются за $O\left(4^{n(n+1)/2}\right)$. Вводя меру «приемлемости» разбиения, можно просто наиболее приемлемое. В качестве меры можно взять $\left(\sum_{x\in S} d^{-1}(x)\right)^{-1}$, где $d(x)$ — расстояние от точки до близжайшей границы.

Короче, труднореализуемое решение. Оказалось проще работать с некрасивыми многоугольниками.