Timeline for Shortest Manhattan-norm paths among disjoint rectangles
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2018 at 0:17 | vote | accept | Chuck Newton | ||
| Jun 19, 2018 at 23:41 | answer | added | Joseph O'Rourke | timeline score: 5 | |
| Jun 19, 2018 at 21:42 | comment | added | Gerhard Paseman | I suspect it will be hard. Imagine a series of m rows of 3 rectangles in each row, where the paths through a row are at distance a and b from "the left". (I am thinking of a and b as randomly chosen from the unit interval.) It strikes me that any preprocessing may need to store 2^m pieces of information. If you can solve this case efficiently, there is hope for a nice solution. Gerhard "Make All Your Obstacles Easy" Paseman, 2018.06.19. | |
| Jun 19, 2018 at 21:17 | comment | added | Chuck Newton | Thanks @GerhardPaseman, they are obstacles. I edited the post. | |
| Jun 19, 2018 at 21:17 | history | edited | Chuck Newton | CC BY-SA 4.0 |
rectangles are obstacles
|
| Jun 19, 2018 at 21:15 | comment | added | Gerhard Paseman | It is unclear what role the rectangles play. Are they obstacles or reservoirs of points? It may be possible for small numbers of obstacles to classify paths through the obstacles and put them in a short list, and use this for your processing. Without more clarity, I hesitate to offer further suggestions. Gerhard "Sees Some Obstructions To Answering" Paseman, 2018.06.19. | |
| Jun 19, 2018 at 20:10 | review | First posts | |||
| Jun 19, 2018 at 20:41 | |||||
| Jun 19, 2018 at 20:00 | history | asked | Chuck Newton | CC BY-SA 4.0 |