Skyline problem with triangular buildings

Question

This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites.

The following are two variations from the usual Skyline problem:

1. Report all points in the skyline, and not just the upper left points.
2. Use arbitrary triangles and report all points in the shape formed by overlapping the triangles, where all triangles have positive height and have a base lying on the $x$-axis. I will call this variant Skyline-TRI. (Can one generalize the case where all the triangles are isosceles or right-angled to the case where the triangles are arbitrary?)

---

How can I solve Skyline-TRI?

For simplicity, assume all triangles are sorted by their leftmost coordinates on the $x$-axis. Each triangle is specified by a quadruple $(x_1,x_2,x_3,h)$, which represents three vertices $(x_1,0), (x_2,0), (x_3,h)$.

I know how to write an algorithm using the Divide and Conquer approach that addresses variation 1, but it only works when all the buildings are rectangles. For the rectangle case of the Skyline problem, the rough idea is to keep track of the leftmost coordinate and to find the correct endpoint of each vertical segment in the skyline. For the triangular case, I think it might be useful to consider two triangles specified by coordinates $(x_{11}, 0), (x_{12},0),(x_{13},h_1)$ and $(x_{21}, 0), (x_{22},0),(x_{23},h_2)$. The leftmost point on the $x$-axis will be on the Skyline of the two triangles and one can use the equations of the lines of the sides of the triangles not on the $x$-axis to compute intersection points, but I'm not really sure how to put the details together to come up with a linear time algorithm. For example, given the two triangles specified by the values $(1,3,-1,5)$ and $(0,2,2,5)$, the resulting Skyline should contain the points $(0,0), (1/2,5/4),(-1,5), (1,5/2), (2,5), (2,5/4), (3,0)$ in that order.

Splitting the problem of finding the skyline of $n$ triangles into two halves on which to recurse is simple, as is the base case where the three points of the triangle are reported/returned.

I'm not sure how to show that the Skyline of $n$ triangles will contain at most $O(n \log n)$ points.

Edit: To clarify, I want to solve this problem using the divide and conquer approach, and not the sweep line technique mentioned in the comments section of this question.

---

One very general solution that doesn't use divide and conquer involves computing all intersections between all sides of the triangles and then finding the convex hull of these points as well as the $O(n)$ points representing vertices of the triangles. This takes $O(n^2 \log n)$ time, which is obviously too slow.

Answer 1

If holes are ignored (only the outline is computed), this is an instance of computing a single face of arrangement of half-lines (rays).

With half-lines, the maximum number of vertices in a single face is $\Theta(n)$. Therefore, this problem can be solved in $\Theta(n \log n)$ expected time using the randomized divide-and-conquer approach. See [1] chap.6.2 for details.

If holes are allowed, the number of vertices is $\Theta(n^2)$ in the worst case. Consider the $n \times n$ grid rotated by 45 degrees. Then, replace each line segment with a very acute triangle.

• [1] P. K. Agarwal and M. Sharir. Davenport-Schinzel sequences and their geometric applications, 2015.