5
$\begingroup$

You are given a set of $n$ rectangles in no particular order. They have varying widths and heights, but their bottom edges are collinear, so that they look like buildings on a skyline. For each rectangle, you’re given the $x$ position of the left edge, the $x$ position of the right edge, and the height. Your task is to draw an outline around the set of rectangles so that you can see what the skyline would look like when silhouetted at night. Source

Drawing in practice I imagine can come in different forms, for example if a building is described by a triple (leftX, height, rightX) then the output can be a left to right ordered list $\{x_{1},h_{1},x_{2},h_{2},x_{3},h_{3},x_{4},h_{4},...\}$ where each $x_{i}$ represents a vertical edge and each $h_{i}$ represents a horizontal edge.

This problem is clearly defined and there are some quite efficient algorithmic solutions, however I could not find anywhere the motivation for this problem. Why would anyone want to solve it? Are there any interesting applications where being able to solve this problem efficiently is important?

$\endgroup$
3
$\begingroup$

The "skyline problem" is an example of finding the Pareto front of a set of points in 2-D space. More generally it's an example of multi-objective optimization which has many applications.

You might find this thread relevant.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.