Skyline Problem

Question 1

What is meant by the skyline problem

Answer 1

To find the outer contours of some overlapping or non-overlapping staples/skylines.

Question 2

What points are you interested in the skyline problem?

Answer 2

A point at every new height.

Question 3

Given n buildings, what is the running time of an algorithm marking each upper-left and lower-right corner, then adjusting corners overlapping with other buildings, then removing redundant key points (at the same height.)

Answer 3

O(n^2) as we need to calculate two points for each building.

Question 4

How does the merge-sort algorithm work?

Answer 4

1. Choose the key points to the left.
2. If its height is less than the height of the previous keypoint (for iteration 2 and on) update it to the same height.