Joe Neeman escreveu:
>
> If there are any references about skylines around, I'd be interested in
> seeing them; I just made things up as I went. Your suggestion (which
There is one thing: you base the structure on lists, which makes for
easy merging, but is relatively expensive if you do lots of point
queries (ie. how high is the skyline at point X). I'm not sure if it is
an issue, and things are definitely better than the previous version, of
course. It should be possible to use a (binary) tree, with the X
position of each event as a sort-key.
I'm not (yet) convinced that it's worth the effort. It seems that querying at a point is the only thing that gets improved speed. Merging and distance are still O(sum of length of skylines) because we need to at least look at every point in every skyline. Building a skyline is still O(n log n).
On the other hand, to implement the tree version, we would need to write a complete balanced tree implementation. Also, the merging and distance algorithms rely a lot on the successor to a node which becomes slower (although only by a constant factor). We lose (a constant factor) again because we can't simply splice() two trees together (if you hadn't noticed, I use splice() quite a bit to avoid copying data).
Querying the height at a point is currently only used in tie-formatting problem and the skylines there are small anyway. Is it something that's likely to become more common?