The skyline problem

Re:The skyline problem by frownie on Tuesday September 02, 2014 @06:14AM (#8256752)

is it me or the algorithm suggested at the end degenerates if the rectangles are organized as the steps of a stair and each of them extends to the rightmost position ? In that case it degenerates because the heap manipulation degenerates...

[ Parent | on HN ]

Re:The skyline problem by brianpgordon on Tuesday September 02, 2014 @09:09PM (#8261060)

I don't think so. No matter what shape the problem is in, there are always exactly n inserts and n deletes to the heap. Those are O(log n) operations, and there are 2n of them, so it's O(n log n).

[ Parent | on HN ]

Re:The skyline problem by wiz21 on Thursday September 04, 2014 @02:56AM (#8267066)

Ahhh read too fast :-( Crucial sentence is "Fortunately, we know about a data structure which can keep track of an active set of integer-keyed objects and return the highest one in O(logn) time: a heap."

But then again. If I read well, he wants to 1st sort the points, 2 iterate over them and using the heap. So we have n log n for the sort and n * n log n for the heap use.. Basically (1+n) n log n (or i'm still tired ? :-))

[ Parent | on HN ]

Re:The skyline problem by brianpgordon on Friday September 05, 2014 @02:29PM (#8275484)

The uses of the heap are:

1. Peek the root of the heap to find the tallest rectangle in the active set. This is a constant time operation.

2. Add a new rectangle to the active set. This is a O(log(n)) operation.

3. Remove a rectangle from the active set. This is a O(log(n)) operation if you use something like a hash table to locate the element in the heap.

Each rectangle is added once (at its left edge) and removed once (at its right edge). The root of the heap is peeked on every critical point. All together, that makes the algorithm O(n log n).

Or am I missing something?

[ Parent | on HN ]