Покрытие n точек с тремя квадратами минимальной длины

Question

Учитывая набор n баллов (a_1, b_1), (a_2, b_2), ..., (a_n, b_n). Необходимо найти минимум x, так что три квадрата axis parallel каждой длины x вместе покрывают все точки.

Я могу найти прямоугольник с наименьшей площадью, охватывающей все точки. Может ли этот прямоугольник каким-то образом использоваться? Или любой намек на то, как подойти к этой проблеме?

Answer 1

Я думаю, достаточно рассмотреть два случая:

1. Когда каждый квадрат затрагивает некоторое ребро наименьшего прямоугольника зоны.
2. Когда два квадрата расположены в противоположных углах прямоугольника с наименьшей площадью, а третий находится внутри (не касается ни одного края прямоугольника с наименьшей площадью).

В первом случае мы могли бы зафиксировать угол одного квадрата в одном из углов 4 прямоугольника, а затем зафиксировать углы других двух квадратов где-то на двух противоположных (для выбранного угла) краев прямоугольника (n возможных позиций для каждого из них), то для каждой точки определяют оптимальный квадрат, где он принадлежит, и минимум x.

Во втором случае попробовать две противоположных пары углов прямоугольника для «внешних» квадратов, то исправить один из углов «внутреннего» квадрата на все n*n положения, определенных всех x и y координат точек, то для каждой точки определения оптимального квадрат, где он принадлежит, и минимум x.

Сложность времени будет O (n).

Answer 2

Ответ @EvgenyKluev, похоже, идет в правильном направлении, но есть несколько тонкостей, которые я хотел бы задать.

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

Размещение квадрата в одном углу прямоугольника (что-то, что вам нужно будет сделать, что достаточно просто доказать) ограничивает пространство поиска для размещения двух других квадратов: пусть A - это набор точек, охватываемых по выровненному по углу первому квадрату, и пусть S - множество всех точек. Возьмите S-A и найдите замкнутый прямоугольник этого набора точек. Размещение оставшихся двух квадратов в противоположных углах охватывающего прямоугольника S-A всегда будет решением (может быть только одна пара противоположных углов), если таковая существует.

Таким образом, один алгоритм может - очень высокий уровень - идти как этот

binary search for x on [0,N]: 
    find R(S), the enclosing rectangle of S 
    for each corner C of R(S): 
     align one square at C, let the points covered by that square be A 
     find R(S-A) 
     do two squares aligned at opposite corners of R(S-A) cover S-A? 

Что касается двоичного поиска, я не могу сказать, как быстро, что будет сходиться к диапазону, что позволяет только одно выравнивание квадраты, в этот момент вы можете непосредственно вычислить значение x - Я ожидаю, что с произвольной точностью вы можете сделать это произвольно плохо. Каждая итерация принимает O (n log n) для сортировки точек в обоих направлениях.