[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: skyline vertical spacing

From: Han-Wen Nienhuys
Subject: Re: skyline vertical spacing
Date: Tue, 14 Nov 2006 15:43:20 +0100
User-agent: Thunderbird (X11/20061107)

Joe Neeman escreveu:
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).

I think you can do better on merging and distance, if you also store min/max heights in nodes; with that you could skip looking at an entire branch of points. However, you're right in that it is premature to optimize this.


Han-Wen Nienhuys - address@hidden -

LilyPond Software Design
 -- Code for Music Notation

reply via email to

[Prev in Thread] Current Thread [Next in Thread]