Here's a patch for introducing skyline vertical spacing. The bulk of the changes are to rewrite skyline so that 1) merging is linear (in the sum of the lengths of the skylines) time 2) building a skyline from boxes is O(n lg(n)) time
3) we support sloped-roof skylines. This isn't used yet, but I think it can be used for skylines where more accuracy is needed (for example in horizontal spacing). In any case, it only adds a constant factor to the complexity.
It would be nice if someone could review my changes particularly in tie-formatting-problem and accidental-placement. output-distance.py is OK with the changes, but I don't really understand the code there.