Timeline for Find rectangle of minimum area where dimensions are larger than minimum
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 8, 2014 at 18:46 | vote | accept | scooz | ||
| Jul 12, 2014 at 8:38 | history | tweeted | twitter.com/#!/StackCompSci/status/487878594912616449 | ||
| Jul 11, 2014 at 19:40 | comment | added | scooz | Pre-processing is allowed, as long as it is bound by memory complexity of up to $O(n)$, and hopefully under $O(n log n)$ runtime complexity. | |
| Jul 11, 2014 at 19:20 | answer | added | user2566092 | timeline score: 2 | |
| Jul 11, 2014 at 12:15 | comment | added | Yuval Filmus | @DavidRicherby Right, this implies that the OP is allowing preprocessing, since otherwise the answer is NO. Also, the restriction on space complexity is needed to rule out the trivial $O(\log n)$ solution requiring quadratic memory. | |
| Jul 11, 2014 at 11:04 | comment | added | David Richerby | Are you allowing preprocessing? You obviously can't do this in better than linear time, otherwise, since you need to look at all the rectangles at least once. | |
| Jul 11, 2014 at 7:21 | comment | added | donkey | Do we have queries of the form $(a,b)$ ? | |
| Jul 11, 2014 at 6:55 | history | edited | Raphael |
edited tags
|
|
| Jul 11, 2014 at 3:58 | answer | added | Yuval Filmus | timeline score: 4 | |
| Jul 11, 2014 at 2:14 | review | First posts | |||
| Jul 11, 2014 at 5:29 | |||||
| Jul 11, 2014 at 1:56 | history | asked | scooz | CC BY-SA 3.0 |