Timeline for Minimum circles to cover a set of points and avoid another set of points
Current License: CC BY-SA 4.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 2, 2020 at 2:02 | history | edited | HEKTO | CC BY-SA 4.0 |
Fix a problem with coverage by external disks
|
| Mar 2, 2020 at 1:41 | comment | added | HEKTO | @j_random_hacker - sorry to say, no... If radii of external disks aren't that large, then there will be areas, not covered by them. However I know, how to fix that | |
| Mar 1, 2020 at 20:38 | comment | added | j_random_hacker | I came to the conclusion that the disks your method creates do cover every $A$-point, which is all you need to ensure that you can always find a solution (if not necessarily an optimal one). The Delaunay triangulation corresponding to the Voronoi diagram already covers (in fact, partitions) the space inside "landlocked" (finite-size) Voronoi cells with triangles, and every such triangle is completely inside a disk that your algorithm creates, so the disks definitely cover all of this area. And I think $A$-points lying in infinite-size Voronoi cells are also covered by some circle. | |
| Mar 1, 2020 at 18:44 | comment | added | HEKTO | @j_random_hacker - also your example shows that my disks might not completely cover my universe, oops! I'll need to make corrections... | |
| Mar 1, 2020 at 18:31 | history | edited | HEKTO | CC BY-SA 4.0 |
Corrected statement about optimal solution
|
| Mar 1, 2020 at 18:10 | comment | added | HEKTO | @j_random_hacker - thank you! Your example shows that my approach is too rigid | |
| Mar 1, 2020 at 16:10 | comment | added | j_random_hacker | I like the Voronoi diagram idea and think this is sufficient to avoid any "gaps" where $A$-points could be hiding, but this doesn't necessarily produce optimal solutions. See e.g. imgur.com/MZsEf09, where black points are in $A$ and red points are in $B$: The solid red disks in the image on the left shows the 3-disk solution you would find, while the solid disks in the right show an optimal 2-disk solution. | |
| Mar 1, 2020 at 1:51 | history | edited | HEKTO | CC BY-SA 4.0 |
Big theta instead of big O
|
| Mar 1, 2020 at 1:27 | history | edited | HEKTO | CC BY-SA 4.0 |
added 7 characters in body
|
| Mar 1, 2020 at 1:10 | history | undeleted | HEKTO | ||
| Mar 1, 2020 at 1:09 | history | edited | HEKTO | CC BY-SA 4.0 |
Correction in the algorithm logic, much more explanations
|
| Feb 29, 2020 at 17:25 | history | deleted | HEKTO | via Vote | |
| Feb 29, 2020 at 15:20 | history | edited | HEKTO | CC BY-SA 4.0 |
Remove step 4
|
| Feb 29, 2020 at 1:59 | history | edited | HEKTO | CC BY-SA 4.0 |
Add step 4
|
| Feb 28, 2020 at 21:54 | history | edited | HEKTO | CC BY-SA 4.0 |
More careful wording
|
| Feb 28, 2020 at 20:54 | history | answered | HEKTO | CC BY-SA 4.0 |