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

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?

Solution

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: