What is this problem? Largest set of contiguous x values for which the same y value can be held

Question

I'm trying to find a linear solution with a small constant factor but I'm not sure what to search for, or even how to succinctly describe it. The best I've come up with is:

Given a set of rectangles on a plane find the set(s) which allow the same y value for some largest contiguous set of x values. All rectangles are axis aligned, the same width, and do not overlap.

I find this much easier to visualize so below is an example problem instance and solution.

Edit:

We have a linear solution that has a constant factor on the order $y_{max} - y_{min}$ which can be pretty big. Here is an idea of the algorithm I've been trying to work out since originally posting this.

• Rectangles are already sorted by $x$ position.
• Maintain an ordered list $I$ of the intervals currently allowing a contiguous line.
• Maintain two variables $(i_{min}, i_{max})$ which are the min and max $y$ value of the current intersection (in the example solution $(5, 5.25)$).
• Iterate from $x_0$ to $x_{max}$

• At each $x$ position test if any of the current rectangle(s) intersect $(i_{min}, i_{max})$.

  • 1) If yes, add the rectangle to $I$ and update $(i_{min}, i_{max})$.
  • 2) If no, find the longest suffix of $I$ s.t. it allows overlap with current rectangle.
  • 3) If no suffix exists or the current $x$ position has no rectangles skip to the next $x$ position with rectangles and reinitialize $I$, and $(i_{min}, i_{max})$.

• In #2 and #3 save the current $I$ if it allows the widest contiguous line so far.

Answer 1

Here is a slightly different algorithm. Start by sorting the list according to the $y$ value. Iterating through all different $y$ values, maintain a list of all rectangles which intersect the given $y$ value, as well as the $x$-intervals that they span. When you lose an interval, you need to split a range. When you add an interval, you need to find which intervals, if any, it is adjacent to, and then enlarge the interval and possible merge two intervals. Some kind of search tree containing all endpoints of the current intervals can be useful for locating the intervals adjacent to a new segment (if they exist). Maintaining the intervals (shortening, splitting, enlarging, joining) should be possible with a Union-Split-Find data structure.

If you use the correct data structures, this algorithm should run in time $O(n\log n)$, where $n$ is the number of intervals. (That's an informed guess.)