Re: skyline vertical spacing

[John Mandereau]

Erik Sandberg wrote:
> Hi,
> 
> I just got another idea of how to improve max-slope skylines. The motivation 
> is mathematical rather than scientific, so there's no guarantee it's a good 
> idea. But anyways:
> 
> The problem that max-slope tries to solve, is to separate objects from each 
> other in X direction as well. My new idea is that what we really want is to 
> separate objects by some minimum Euclidean distance (i.e. x^2+y^2); this can 
> be achieved with skylines if the skyline is formed as circles around each 
> object, and the spacing between skylines is set to 0, as in:
> 
> ========================
> ________     ____________
>         |   |    ___
>         | | |   /   \
>         | | |   | o |
>   ___   | o |   | | |
>  /   \  \___/   | | |
> _| o |__/   \___|   |___
>    |      o          
> ===|======|=============
> 
> The minimum Euclidean distance between objects is then twice the radius. It 
> would probably be sufficient to approximate circles with regular octagons (as 
> in the ascii art :) ), this should also be performance-friendly. It may also 
> be useful to use ellipses rather than circles, if we want more padding along 
> one axis.

I'm not a programmer, only a math student, but why not using a simpler
distance which is even more performance-friendly, like:

Distance:        d_1((x,y),(x', y'))       d_infinity((x,y),(x',y'))
                 = a|x' - x| + b|y' -y|    = Max ( a|x' -x|, b|y' - y| )

                  
                       /\                                 ________
resulting "circle"    /  \                               |        |
                     /    \                              |        |
(in fact, a square   \    /                              |        |
in both cases)        \  /                               |________|
                       \/

where a and b are positive real numbers that can be adjusted.

I don't know if one of these distances would be optimal for skyline
spacing, though.

Cheers,
-- 
John Mandereau <address@hidden>