Timeline for Efficient algorithms for vertical visibility problem
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 11, 2015 at 9:58 | answer | added | No One in Particular | timeline score: 0 | |
| Sep 2, 2014 at 18:32 | comment | added | mnbvmar | I tried hard to make it as different from the original problem as possible :). The original problem was from a local olympiad in informatic and it could be restated as follows: "given a directed acyclic graph, we remove each vertex $v$ and check the longest path in such new graph, call it $l(v)$; find $\min l(v)$". Using some transformations ("an excercise for the reader") we find out that we can make it in $O(n+m)$ plus an instance of vertical visibility problem. If we could do this one in $O(n+m)$, then also we would be able to solve the original problem in linear time. | |
| Sep 1, 2014 at 15:04 | comment | added | vzn | this model looks well defined/ abstracted formally (nice work on that, not an easy feat) however it is always nice to understand the bigger picture as far as what is the context/ application/ bkg etc of this problem? ps on quick look it seems like it might be related to set cover... | |
| Sep 1, 2014 at 6:27 | answer | added | invalid_id | timeline score: 1 | |
| Aug 31, 2014 at 9:34 | comment | added | mnbvmar | @invalid_id Could you please elaborate on this method? That is because I have no idea how to "keep track of the overall maximum" efficiently? Sometimes the maximum may decrease in a strange way. Look at $x=2$ and $x=3$ in the example above. Before $x=2$ the heights of the segments were $2, 5$ (max 5); then they were $2, 3, 5$ (max 5), but then 5 disappeared and max was = 3. How would you deal with this? | |
| Aug 30, 2014 at 7:51 | comment | added | invalid_id | @mnbvmar maybe a dumb suggestion, but how about an array of size $n$, the you sweep and stop every cell $O(n)$. For evry cell you know max $y$ and you can enter it in the matrix, furthermore you can keep track of the overall maximum with a variable. | |
| Aug 29, 2014 at 15:43 | comment | added | mnbvmar | @invalid_id Yes, I tried. However, in this case the sweep line must react appropriately when it meets the beginning of the segment (in other words, add the number equal to segment's $y$-coordinate to the multiset), meets the end of the segment (remove an occurence of $y$-coordinate) and output the highest active segment (output maximum value in the multiset). I have not heard of any data structures letting us do this in (amortized) constant time. | |
| Aug 29, 2014 at 12:15 | comment | added | invalid_id | Did you try sweeping from the left to right? All you need is sorting on $x1$ and $x2$ both in $O(m)$ and $O(m)$ steps to walk to the right. So in total $O(m)$. | |
| Aug 29, 2014 at 10:24 | history | edited | Raphael |
edited tags
|
|
| Aug 29, 2014 at 4:50 | comment | added | D.W.♦ | @babou, the question specifies counting sort, which as the question says, runs in linear time ("linear time using a variation of counting sort"). | |
| Aug 28, 2014 at 23:16 | history | tweeted | twitter.com/#!/StackCompSci/status/505131747642986497 | ||
| Aug 28, 2014 at 22:22 | comment | added | babou | How fast do you sort your m segments? | |
| Aug 28, 2014 at 21:55 | history | edited | mnbvmar | CC BY-SA 3.0 |
elaborated on the find-union algorithm
|
| Aug 28, 2014 at 19:45 | review | First posts | |||
| Aug 28, 2014 at 21:30 | |||||
| Aug 28, 2014 at 19:42 | history | asked | mnbvmar | CC BY-SA 3.0 |