tag:blogger.com,1999:blog-6631959045176600347.post8762866188569806363..comments2017-05-16T23:57:58.175-07:00Comments on Thoughts about software craftsmanship: The Skyline problemSzabolcs Andrásihttp://www.blogger.com/profile/12211719425471873211noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-6631959045176600347.post-86639258943730505702015-07-23T15:05:51.544-07:002015-07-23T15:05:51.544-07:00The combine step runs in linear time because the m...The combine step runs in linear time because the mergePoints function takes two lists and in each recursive step it either "consumes" the first element of the first list, or the first element of the second list, or if the first elements have the same x value, they are removed from both lists. The next recursive iteration is therefore called with lists where either one or both of them are shorter by one than in the previous iteration. This can be repeated n1 + n2 times at most.<br /><br />As for your second question I believe that with a data structure that supports binary search the position of the build could indeed be found in log(n1) time. The inserted building's height, however, can adjust the points of the skyline that are to the right of the building, and in the worst case it changes all the points in the visible skyline.<br /><br />And last but not least the number of Pk points depends on the number of buildings that are currently visible in the skyline and they overlap with the new building. I'm not sure if an exact number or formula can be given here. If, for example, every building inserted into the skyline so far got taller and narrower at the same time, then the shape of the skyline will look like a pyramid. If the nth building inserted into this skyline is a huge rectangle that overlaps with all the existing skyline points then the number of Pk points is going to be (n - 1) * 2. If, however, this huge rectangle building is inserted first and then the rest of the buildings then essentially there is no need to update any skyline points.Szabolcs Andrásihttp://www.blogger.com/profile/12211719425471873211noreply@blogger.comtag:blogger.com,1999:blog-6631959045176600347.post-86360974757493336392015-07-23T10:18:46.334-07:002015-07-23T10:18:46.334-07:00Could you please explain why in the final version,...Could you please explain why in the final version, a single combine step runs in O(n1+n2) and not O(n1*n2)? I'm not sure about steps 2 and 4 in the inductive solution:<br /><br />2. Otherwise find the first Pi(x, h) point of the skyline which immediately precedes lj, the left coordinate of the building Bj, that is xi < lj ≤ xi + 1. Save hi to H if there is such a Pi point, otherwise set H to 0.<br /><br />Wouldn't the search be at best O(logn1), if we use binary search? Then it would be repeated for each point in n2, so if it's O(logn1) repeated n2 times, wouldn't it contribute O(n2*logn1) to the final running time?<br /><br />4. <br />For every Pk(x, h) point where lj ≤ xk < rj replace Pk with P(xk, hj) if hj > hk and hj ≠ hk - 1, or remove Pk if hj ≥ hk and hj = hk - 1. Save hk to H.<br /><br />How many Pk points are there? Wouldn't the worst case be n1 points? Then wouldn't it be repeated for each point in n2, contributing O(n1*n2) to the final running time?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6631959045176600347.post-40114338173140128292013-05-27T07:06:55.146-07:002013-05-27T07:06:55.146-07:00What if every new building merged into the skyline...What if every new building merged into the skyline makes it wider and wider (that is a new building overlaps with all the points of the Skyline)? Even if the skyline points stored in some sorted data structure so that we can look up the closest coordinates in linearithmic time, the height of all the existing skyline coordinates may need to be adjusted in which case the algorithm still runs in quadratic time.Szabolcs Andrásihttp://www.blogger.com/profile/12211719425471873211noreply@blogger.comtag:blogger.com,1999:blog-6631959045176600347.post-45934410505084951102013-05-25T21:38:25.386-07:002013-05-25T21:38:25.386-07:00Could implementation 2 not be run in n*logn time? ...Could implementation 2 not be run in n*logn time? Your implementation is n^2 because every building added to the skyline requires iterating over every existing coordinate in the skyline. If the skyline were stored as a sorted list or binary tree, you could find the closest coordinates to the new building in log(n) time.Anonymousnoreply@blogger.com