2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Прямоугольное разбиение плоскости по опорным точкам
Сообщение30.01.2015, 23:32 
Аватара пользователя
Задача не разрешена, но потеряла актуальность (остановился на диаграммах Вороного, не столь удобных, но понятных и уже реализованных в стандартных библиотеках)

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

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

 
 
 [ Сообщений: 2 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group