Timeline for Find all polygons from a set that overlap a given polygon (convex case)
Current License: CC BY-SA 4.0
33 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23 at 12:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Jul 26 at 11:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Mar 28 at 10:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Nov 29, 2023 at 10:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 1, 2023 at 9:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 3, 2023 at 7:07 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 4, 2022 at 7:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 6, 2022 at 6:06 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 8, 2022 at 6:05 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 9, 2021 at 6:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 11, 2021 at 6:00 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 13, 2021 at 5:01 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 14, 2020 at 4:09 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 16, 2020 at 3:08 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 18, 2020 at 3:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Dec 20, 2019 at 3:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Aug 22, 2019 at 9:29 | comment | added | greybeard | The benefit of 2d-trees (and (iso-oriented) bounding-boxes) "obviously" depends on the "diagonality" of the polygons $S_i$ (the area ratio of $S_i$ to its bounding-box). Has using a "non-base" (say, three vectors (spaced, say, 120°) for two-dimensional objects) been explored/described? | |
| Aug 22, 2019 at 3:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| Apr 24, 2019 at 11:42 | comment | added | Peter Taylor | Convex polygons are trivial to triangulate, and we're given that the $S_i$ and $P$ have $O(1)$ vertices, so wlog we can assume that the $S_i$ and $P$ are triangles. That still doesn't seem to make it trivial, but it might make it easier. | |
| Apr 24, 2019 at 2:02 | history | bumped | CommunityBot | This question has answers that may be good or bad; the system has marked it active so that they can be reviewed. | |
| S Mar 25, 2019 at 1:31 | history | edited | Wandering Logic | CC BY-SA 4.0 |
TeXify question
|
| S Mar 25, 2019 at 1:31 | history | suggested | BearAqua the Logician | CC BY-SA 4.0 |
TeXify question
|
| Mar 24, 2019 at 21:31 | review | Suggested edits | |||
| S Mar 25, 2019 at 1:31 | |||||
| Mar 24, 2019 at 21:04 | answer | added | D.W.♦ | timeline score: 0 | |
| Mar 23, 2019 at 21:05 | comment | added | aycarus | Yes, the set of polygons {P_i, i=1..M} could be known in advance if it leads to a better solution. | |
| Mar 23, 2019 at 20:51 | comment | added | D.W.♦ | Cool. Any chance the polygons P are known in advance? I think I can see how to do it efficiently if all the P's are provided in advance. If you have to do it on the fly it seems more challenging. | |
| Mar 23, 2019 at 20:29 | comment | added | aycarus | This is a practical problem so nothing needs to be proved theoretically. Yes there is flexibility, but O(N^2) is unacceptable. Yes we can assume the {S_i} are disjoint, but often have coincident edges (although this is not guaranteed). There is always the possibility they could be "really nasty" -- but we want O(log N) performance for the "not nasty" case. | |
| Mar 23, 2019 at 17:56 | comment | added | D.W.♦ | Is this a practical problem, or a theoretical one? Do you care more about it working well in practice or about provable worst-case bounds? Does the running times have to be exactly $O(n \log n)$ and $O(\log n)$, or do you have some flexibility (e.g., for it to be $O(n \log n + k)$ where $k$ is often small; or $O(n \log^2 n)$; to use amortized running time instead of worst-case running time; etc.)? Can we assume the polygons $S_1,\dots,S_n$ are disjoint? Can we assume that they usually won't be "really nasty" (e.g., lots of long and skinny shapes in an inconvenient configuration)? | |
| Mar 23, 2019 at 6:00 | history | edited | aycarus | CC BY-SA 4.0 |
added 6 characters in body
|
| Mar 23, 2019 at 6:00 | comment | added | aycarus | Sorry, yes. I meant to say O(N log N) initialization time. Of course, that is the time required to build the kd-tree. Also yes we can assume each convex polygon has only O(1) vertices. The problem came up in the course of research on data regridding problems. | |
| Mar 23, 2019 at 1:14 | comment | added | D.W.♦ | I suggest studying en.wikipedia.org/wiki/Line_segment_intersection and en.wikipedia.org/wiki/Bentley%E2%80%93Ottmann_algorithm and related ideas. | |
| Mar 23, 2019 at 1:12 | comment | added | D.W.♦ | Can you credit the original source where you encountered this? Also, are you sure that only $O(N)$ time is acceptable, and $O(N \log N)$ time is not acceptable? Can we assume that each convex polygon has only $O(1)$ vertices? | |
| Mar 22, 2019 at 23:26 | history | asked | aycarus | CC BY-SA 4.0 |