Coverage of n points with three squares of minimum length

Question

Given a set of npoints (a_1, b_1), (a_2, b_2), ..., (a_n, b_n). It is necessary to find a minimum xso that three squares axis paralleleach of the length xtogether cover all points.

I can find the rectangle with the smallest area covering all points. Can this rectangle be used in some way? Or any hint on how to approach this problem?

Answer 1

I think it’s enough to consider two cases:

• When each square touches any edge of the smallest rectangle.
• , - ( - ).

, - ( ) (n ), , , x.

"" , "" n*n, x y, , , x.

O (n ³).

Answer 2

@EvgenyKluev, , , , .

x, , x , , x, ( integer 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) .