CODEWITHSUNDEEP
algorithm
Ma Ming
Ma Ming

Reputation: 1895

How to find the narrowest band covering given points in the 2D space?

Given n points in the 2D space, I want the find the narrowest band covering these points. In other words, I want to find two parallel lines such that all points fall between these two lines. Are there exiting an effective algorithm?

Upvotes: 2

Views: 113

Answers (1)

DAle
DAle

Reputation: 9127

First, these lines should go through the points that form the convex hull of our points. Convex hull could be found by many different algorithms. The choice depends on your data.

enter image description here

Second, one of our parallel lines will go through the convex hull segment. Because we can rotate both parallel lines decreasing a distance between them till we stop at the other point of the convex hull.

enter image description here

Now, we should iterate through all convex hull segments, and for every segment, build a line going through this segment, and find convex hull point that is farthest from this line. Minimum of all these distances (from the farthest point to the line) would be the answer. All this iteration can be done in linear time using rotating calipers (thanks to MBo).

Upvotes: 4

Related Questions