Timeline for Area of the union of rectangles anchored on the x-axis
Current License: CC BY-SA 3.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2020 at 10:30 | history | edited | CommunityBot |
Commonmark migration
|
|
| Dec 1, 2012 at 7:03 | comment | added | Merbs | @com, do you want to answer your own question? | |
| May 24, 2012 at 19:26 | comment | added | Joe | The bottom edge of the rectangles on the x axis is a nice simplification. This looks a lot like a skyline... | |
| May 24, 2012 at 18:08 | comment | added | com | @JeffE, I like your comments. It looks like I need all $y$'s that lower than the current $y$, all there $y$'s I insert to status data structure. From data structure I need to pull the maximum $y$ from all y's in status, so sorted list should be sufficient. | |
| May 24, 2012 at 15:48 | comment | added | JeffE | Think about what you want the data structure to do, not the implementation details of how it should do it. Abstract data type, not concrete data structure. And no, you don't need the $y$ coordinates of all the intersection points, just some of them. But which ones? | |
| May 24, 2012 at 8:58 | comment | added | com | @JeffE, I assume we don't need intersection points at all, only $y$ coordinate of intersection points. And I really don't have an idea where to store them if not in tree. | |
| May 24, 2012 at 8:21 | comment | added | JeffE | @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. | |
| May 24, 2012 at 4:12 | comment | added | com | and in the case when status data structure is tree, O(nlogn)? | |
| May 23, 2012 at 20:48 | comment | added | Vinayak Pathak | I don't think it will be $O(n\log n)$. When your sweeping algorithm is right in the middle in the bad example that I mentioned, you will have n things stored in the queue. But an adversary can make the right edges of these n rectangles occur in any order. Since whenever you find a right edge, you need to decide which rectangle to remove from your queue, each of these events might take linear time to process. Linear number of events with linear processing time for each is $O(n^2)$. | |
| May 23, 2012 at 20:23 | history | edited | Gilles 'SO- stop being evil' | CC BY-SA 3.0 |
typos
|
| May 23, 2012 at 18:31 | comment | added | com | @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 | |
| May 23, 2012 at 17:31 | comment | added | Vinayak Pathak | So, btw, the combinatorial complexity of the union can be at most O(n) because each rectangle can contribute to only a constant number of turns on the boundary. | |
| May 23, 2012 at 17:30 | comment | added | Vinayak Pathak | 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. | |
| May 23, 2012 at 17:16 | history | tweeted | twitter.com/#!/StackCompSci/status/205346432645996546 | ||
| May 23, 2012 at 13:28 | comment | added | Syzygy | Your approach should work, if I understood it correctly. Since the only event points are left and right boundary points of rectangles, the number of event points stays in $O(n)$. Intersection points are never computed or considered. Preprocessing takes $O(n\log n)$, and processing an event point costs constant. | |
| May 23, 2012 at 12:43 | comment | added | com | Neither do I. I'll ask my teacher later. In your opinion does the ideal look good? | |
| May 23, 2012 at 12:38 | comment | added | Syzygy | 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. | |
| May 23, 2012 at 12:36 | comment | added | Vinayak Pathak | Your solution is not really optimal. The number of intersections could be $\Omega(n^2)$ in the worst case. As Syzgy points out, a better solution can be constructed. Hint: think divide and conquer. | |
| May 23, 2012 at 12:32 | history | edited | com | CC BY-SA 3.0 |
added 67 characters in body
|
| May 23, 2012 at 12:31 | comment | added | com | The complexity of sweep line algorithm is $O((n+l)logn)$, where $l$ - number of intersections.Because we don't consider intersection, the complexity I assume is $O(nlogn)$ | |
| May 23, 2012 at 12:13 | comment | added | Syzygy | What is the complexity of your approach? I can think of an $O(n\log n)$ solution. | |
| May 23, 2012 at 11:25 | history | asked | com | CC BY-SA 3.0 |