On 11/14/06, *Han-Wen Nienhuys* <address@hidden
<mailto:address@hidden>> wrote:
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).