Today, I started thinking about the complexity of a certain geometric problem: finding the horizon of a set of convex objects. In this post, I'll first state the problem and then attempt to explain why this is an interesting problem to think about.
The Convex Horizon Problem
Given a list of 2D convex objects, return a function h that maps each x-coordinate to the maximum y-coordinate such that (x, h(x)) is contained in some object. This is the "horizon" or "skyline" of the objects.
First Reduction: when working with convex polygons, this is equivalent to finding the horizon of a series of line segments; or, equivalently, trapezoids with bottom edges at negative infinity. So this is the version of the problem I'll be thinking of:
(The horizon of the many-hued trapezoids is the thick black polyline.)
Thoughts on Complexity
Any algorithm that computes such a horizon must spend time at least linear in the number of output points in the horizon line. So it's interesting to think about how many points this could be. Particularly, I find this intriguing because of two different (related) problems.
The Box Horizon problem pretty clearly has output of size at most 4N (for N boxes). The argument goes something like: the horizon is a chain of line segments alternating between flat segments and vertical segments. The vertical segments correspond to the vertical edges of boxes, and each box edge appears at most once in the list. This means there are at most 2N vertical segments, which must (therefore) separate at most 2N horizontal segments.
(Mind you, the time complexity of an algorithm that computes a box horizon from an unsorted set of boxes is likely O(N log N), given as reducing sorting to box horizon seems likely to be trivial.)
The logic used to argue for the output complexity of box horizon breaks for trapezoid horizon because the topmost trapezoid can switch not just at an edge, but at a line segment intersection. And it's easy to see that there can be quadratically many intersections among lines:
But this standard lines example doesn't have a clear translation to the trapezoid horizon setting! So that leaves an interesting puzzle: is there some other argument that can be used to demonstrate linear output complexity of trapezoid horizon? Or, failing that, what's a super-linear output complexity example for this setting?
I plan to ponder this more over the next few days. If you have some ideas, feel free to get in touch.
