CODEWITHSUNDEEP
algorithmgraphicsgeometry2d
glutz
glutz

Reputation: 1959

How to find the minmal bounding rectangles for a set of lines?

Provided a set of N connected lines on a 2D axis, I am looking for an algorithm which will determine the X minimal bounding rectangles.

For example, suppose I am given 10 lines and I would like to bound them with at most 3 (potentially intersecting) rectangles. So if 8 of the lines are clustered closely together, they may use 1 rectangle, and the other two may use a 2nd or perhaps also a 3rd rectangle depending on their proximity to each other.

Thanks.

Upvotes: 3

Views: 298

Answers (1)

Per
Per

Reputation: 2634

If the lines are actually a path, then perhaps you wouldn't be averse to the requirement that each rectangle cover a contiguous portion of the path. In this case, there's a dynamic program that runs in time O(n2 r), where n is the number of segments and r is the number of rectangles.

Compute a table with entries C(i, j) denoting the cost of covering segments 1, …, i with j rectangles. The recurrence is, for i, j > 0,

C(0, 0) = 0
C(i, 0) = ∞
C(i, j) = min over i' < i of (C(i', j - 1) + [cost of the rectangle covering segments i' + 1, …, i])

There are O(n r) entries, each of which is computed in time O(n). Recover the optimal collection of rectangles at the end by, e.g., storing the best i' for each entry.

I don't know of a simple, optimal algorithm for the general case. Since there are “only” O(n4) rectangles whose edges each contain a segment endpoint, I would be tempted to formulate this problem as an instance of generalized set cover.

Upvotes: 2

Related Questions