Наименьшее множество прямоугольников, описывающих множество целых точек - PullRequest
Новая
       67

Наименьшее множество прямоугольников, описывающих множество целых точек

0 голосов
/ 16 июля 2009

Учитывая набор N-мерных целочисленных точек, как найти наименьший набор N-мерных кубоидов (прямоугольники в 2-м случае), чтобы целая точка находилась в наборе целочисленных точек тогда и только тогда, когда он содержится в одном или нескольких кубоидах / прямоугольниках. Целочисленная точка означает точку с целочисленными координатами.

например. с учетом точек (1,0), (2, 0) и (3,1), (4,1) наименьший набор прямоугольников равен (1,0-2,0), (3,1-4,1 ), см. диаграмму ниже: 

2 .....
1 ...##
0 .##..
  01234

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

Ответы [ 3 ]

2 голосов
/ 13 декабря 2009

Общий случай NP-сложен:
http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1988.21976

Похоже, его можно приблизить к O (log N). См. «Сборник проблем оптимизации NP» в Интернете, найдите «МИНИМАЛЬНАЯ КРЫШКА ПРЯМОУГОЛЬНИКА»

Кроме того, возможно, что ваш конкретный вариант использования может быть эффективно решен.

1 голос
/ 02 декабря 2009

Я предполагаю, что вы готовы терпеть перекрывающиеся прямоугольники, поскольку, если точки равны 

4 .###.
3 ..#..
2 .###.
1 ..#..
0 .###.
  01234

тогда вы можете покрыть четырьмя перекрывающимися прямоугольниками, но потребуется пять непересекающихся.

Как насчет этого алгоритма:

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

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

Обратите внимание, что в приведенном выше примере вы получите три прямоугольника: один вертикальный и два горизонтальных.

1 голос
/ 16 июля 2009

Существует множество подходов к поиску существующих точек:

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

  2. Если у вас есть одна или несколько координат Z, соберите точки в растровом изображении (глубина 1 бит). Просто включите пиксель в растровом изображении.

  3. Если вам действительно нужно собрать точки в прямоугольниках, вы должны сначала поместить их в упорядоченный набор (по координатам). Повторяйте этот набор много раз. Каждый раз принимайте первую точку из набора. Затем найдите любую точку, которая является соседом слева / справа от той, которая у вас уже есть. Если есть, объедините их в (горизонтальную) линию. Расти эту линию, когда получишь больше очков.

Когда не осталось точек, сделайте то же самое для линий, чтобы вырастить прямоугольники.

...