8
$\begingroup$

I am trying to solve the following computational geometry problem.

Let $S$ be a set of $n$ axis-parallel rectangles in the plane, so that the bottom edge of each rectangle in $S$ lies on the $x$-axis.

  1. What is (an upper bound on) the combinatorial complexity of the union $K$ of the rectangles in $S$?
  2. Give an efficient algorithm for computing the union and its area.

I suggest using sweep line algorithm for the purpose of computing union of areas. First we should consider queue of events. Events are just the leftmost and the rightmost $x$'s of rectangle. As in standard interpretation all $x$'s should be sorted.

Start iterations on event queue (like in standard algorithm). On every new event we can compute an area we've already covered. When two or more rectangles intersect (can be identified by data structure) we should pick the rectangle with the biggest $y$-coordinate until the next event.

That's a general idea. The main difference from the classic sweep line algorithm is that we don't have to compute intersection and inserting them to queue. All we are interested in is intersection of rectangles which occur on vertical lines of leftmost $x$ and rightmost $x$.

I am not completely sure that the solution I presented is the correct one. This exercice was marked with high complexity grade. Maybe I missed something?

In addition, I don't know how to answer the first question.

Improve this question
$\endgroup$
17
  • 3
    $\begingroup$ What is the complexity of your approach? I can think of an $O(n\log n)$ solution. $\endgroup$
    – Syzygy
    Commented May 23, 2012 at 12:13
  • 2
    $\begingroup$ What exactly do you mean with the "combinatorial complexity of the union"? Do you mean the complexity of computing the union? I am not familiar with the notion of complexity of a region. $\endgroup$
    – Syzygy
    Commented May 23, 2012 at 12:38
  • 3
    $\begingroup$ The standard definition of combinatorial complexity of the union is the number of vertices in the boundary, i.e., the number of places where the boundary takes a "turn". Your approach will perform badly for the following example: rectangle 1 starts at x coordinate 0 and ends at x coordinate n and has a height 1, rectangle 2 starts at x coordinate 1 and ends at x coordinate n-1 and has height 2, rectangle 3 starts at 2 and ends at n-2 with height 3 and so on. $\endgroup$
    – Vinayak Pathak
    Commented May 23, 2012 at 17:30
  • 1
    $\begingroup$ @VinayakPathak, thank you very much for the comments. You described exactly the worst case scenario and it's time complexity is $O(nlogn)$. Thanks for the definition of combinatorial complexity $\endgroup$
    – com
    Commented May 23, 2012 at 18:31
  • 3
    $\begingroup$ @com: There isn't just one "sweepline algorithm". What information do you need to maintain about the intersection of the sweepline and the rectangles? (Hint: It's not the complete sorted list of intersection points.) What data structure efficiently maintains that information as things are inserted and deleted? (Hint: It's not a "queue" or a "tree".) Also, Vinayak's comment is incorrect — When the sweepline reaches the right edge of rectangle $i$, you must delete rectangle $i$ from the data structure. There is nothing to decide. $\endgroup$
    – JeffE
    Commented May 24, 2012 at 8:21

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.