The contour of a collection of shapes is the boundary of the intersection of the

Question

The contour of a collection of shapes is the boundary of the intersection of these shapes against the space. For examples, the red line surrounding the rectangles below is the contour of the shapes. In this problem you will explore algorithms that compute the contour of access-aligned rectangles (upright) that are with bottom edges collinear (all bottom edges of the rectangles are incident on the x-axis) as shown below on the right.

Problem statement: Given a collection of rectangles R of size n, where a rectangle is given by a pair of vertices: the upper left corner and the lower right corner and for each rectangle the lower corner vertices lie on the x-axis, compute the contour C of the set.

Input: Set rectangles expressed as a pair of points: one for the upper left corner and one for the lower right corner. Output: Set of vertices that describe the contour of the set of rectangles.

1. Describe a divide and conquer algorithm to compute the contour of the set of rectangles. What’s the running time of the algorithm?

Explanation / Answer

The approach you outline is simple and useful, but suffers from terrible artifacts as shown. Avoid it. You need a parallel growth algorithm; for a single-threaded model, a round-robin approach follows:

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.