Как равномерно распределить N точек на M зон?
1,00
р.
Дано двумерное пространство. Даны N точек с заданными координатами. Нужно распределить точки в M зон. В каждую зону нужно поместить количество точек равное целому частному M/N или M/N+1. Способ определения кому достанется M/N, а кому M/N+1 значения не имеет. Внешний контур зон должен быть выпуклым. Зоны не должны пересекаться, а если это невозможно, то в пересечении зон, не должно быть внутренних точек.
Например,
Следующий вариант плохой
Я затрудняюсь перенести это условие на формальный язык. В реальной задаче (N>5000, M~50) вариант с красными стрелками не подходит, потому что для "коммивояжеров" получится слишком неудобный участок
Похожие вопросы
Поиск геометрического центра группы объектов в 3D пространстве с предварительной фильтрацией Какой существует алгоритм для объединения точек в области? Структура данных для упорядочения двумерных точек
Ссылки по теме
Хабрахабр. Андрей Часовских @andreycha. Обзор алгоритмов кластеризации данных.
Ответ
Точное решение с доказательством я привести не могу, но могу дать несколько направлений.
Первый вариант
Можно построить частный случай Kd-дерева, когда каждой области принадлежит по 1 точке, а после начать объединять области снизу, используя данное условие. Если точки находятся "близко", то они будут соседями на соседних уровнях, и поэтому объединятся в первую очередь.
Второй вариант
Второй вариант предполагает построение диаграммы Вороного. Для каждой точки находим ближайшие границы. Области можно объединять только с областями, которые смежные с данными границами. В данном случае будет усеченный перебор, так как в среднем у каждой точки будет мало таких границ. Худший случай - точки расположены строго по гексагональной сетке.
Рекомендую посмотреть "Mark de Berg - Computational Geometry Algorithms and Applications". Там будет описание построения данных структур.
Я бы начал с первого варианта, так как Kd деревья реализуются достаточно просто и информации по ним больше, возможно, даже можно найти пример с объединением по условию, так как эти деревья имеют много применений. Диаграммы Вороного проще "дебажить" графически и есть много реализаций на разных языках, поэтому базу можно быстрее сделать.
Если отталкиваться от "в приоритете близость точек друг к другу и равное количество для каждой зоны", то диаграммы Вороного могут быть лучше, так как у них при построении похожая задача стоит. Возможно, можно доказать транзитивность этого условия между областями. Тогда достаточно будет построить диаграмму второго порядка, их в книге вроде нет, но можно найти несколько статей на эту тему. К сожалению, готовых реализаций для диаграмм высших порядков я не встречал, поэтому придется писать самостоятельно.
Например,
Следующий вариант плохой
Я затрудняюсь перенести это условие на формальный язык. В реальной задаче (N>5000, M~50) вариант с красными стрелками не подходит, потому что для "коммивояжеров" получится слишком неудобный участок
Похожие вопросы
Поиск геометрического центра группы объектов в 3D пространстве с предварительной фильтрацией Какой существует алгоритм для объединения точек в области? Структура данных для упорядочения двумерных точек
Ссылки по теме
Хабрахабр. Андрей Часовских @andreycha. Обзор алгоритмов кластеризации данных.
Ответ
Точное решение с доказательством я привести не могу, но могу дать несколько направлений.
Первый вариант
Можно построить частный случай Kd-дерева, когда каждой области принадлежит по 1 точке, а после начать объединять области снизу, используя данное условие. Если точки находятся "близко", то они будут соседями на соседних уровнях, и поэтому объединятся в первую очередь.
Второй вариант
Второй вариант предполагает построение диаграммы Вороного. Для каждой точки находим ближайшие границы. Области можно объединять только с областями, которые смежные с данными границами. В данном случае будет усеченный перебор, так как в среднем у каждой точки будет мало таких границ. Худший случай - точки расположены строго по гексагональной сетке.
Рекомендую посмотреть "Mark de Berg - Computational Geometry Algorithms and Applications". Там будет описание построения данных структур.
Я бы начал с первого варианта, так как Kd деревья реализуются достаточно просто и информации по ним больше, возможно, даже можно найти пример с объединением по условию, так как эти деревья имеют много применений. Диаграммы Вороного проще "дебажить" графически и есть много реализаций на разных языках, поэтому базу можно быстрее сделать.
Если отталкиваться от "в приоритете близость точек друг к другу и равное количество для каждой зоны", то диаграммы Вороного могут быть лучше, так как у них при построении похожая задача стоит. Возможно, можно доказать транзитивность этого условия между областями. Тогда достаточно будет построить диаграмму второго порядка, их в книге вроде нет, но можно найти несколько статей на эту тему. К сожалению, готовых реализаций для диаграмм высших порядков я не встречал, поэтому придется писать самостоятельно.
