Skyline Algorithm – Divide and Conquer

Give a list of tuples – where each tuple has 3 value – (x1, x2, h1) – each tuple represents a rectangular block of a building in the city skyline.

x1 – Start Coordinate of a Block on X Axis
x2 – End Coordinate of a Block on X Axis
h1 – Height of the block

Once a list of such tuples is given he problem is to find out the general skyline of the City int he 2D plane – where 1 building’s coordinates could be overlapping with another building and changing the skyline from a 2D perspective

For Example if we have a set of tuples as below


The general skyline algorithm should return

(1,4,10), (4,6,12), (6,9,15), (9,15,12)

I use a recursive Divide and Conquer Algorithm where I break up the original list into a list of smaller tuples.
When there is only 1 or 2 tuple in a list – we call the merge() routine to merge 2 tuples.

The results are printed as a set of blocks using matplotlib graphing library


Command Line
python 1 4 10 4 6 12 6 9 15 9 15 12

// where you have a set of 3 numbers – which represents a tuple and
// have any number of such tuples

// the program exits if any number is a -ve number and if the
// number of entries is not a multiple of 3

The code finally generates a graph of the Skyline using matplotlib python library – something like the one below



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s