CODEWITHSUNDEEP
algorithmdata-structuresgraphgeometry
HimanshuArora9419
HimanshuArora9419

Reputation: 737

enclose maximum no of point inside square of length l

What would be the algorithm for given problem statement? Given n points in 2D plain you need to find square(sides parallel to axes) of side length l which cover maximum no of points from given n points?

output should be bottom-left coordinate of square and no of point it enclose.

Upvotes: 0

Views: 865

Answers (1)

coproc
coproc

Reputation: 6247

A brute force algorithm based on the idea that any solution can be moved upwards and to the right until the lower and left sides contain a point:

for all pairs of points try to construct a square with side length l with one point of the pair on the left side and one points of the pair on the lower side. If this is possible count the number of points in it. Keep the square with the maximal number of points.

Upvotes: 1

Related Questions