Re:The skyline problem
by cperciva on Tuesday September 02, 2014 @03:37AM
(#8256215)
I believe the problem can be reduced to sorting
Speaking of which: Given values 0 < a_i < A for some A, apply the skyline algorithm to the rectangles a_i < x < A, 0 < y < a_i. The resulting sequence of heights gives you the values a_i sorted in increasing order; thus the skyline problem cannot be solved in less than O(n log n) time.
Speaking of which: Given values 0 < a_i < A for some A, apply the skyline algorithm to the rectangles a_i < x < A, 0 < y < a_i. The resulting sequence of heights gives you the values a_i sorted in increasing order; thus the skyline problem cannot be solved in less than O(n log n) time.