Timeline for Shortest path through $\sqrt{n}$ points out of $n$
Current License: CC BY-SA 3.0
12 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 17, 2014 at 1:20 | answer | added | Douglas Zare | timeline score: 8 | |
| Jul 16, 2014 at 23:05 | vote | accept | Kellar | ||
| Jul 16, 2014 at 4:17 | vote | accept | Kellar | ||
| Jul 16, 2014 at 4:17 | |||||
| Jul 16, 2014 at 0:23 | answer | added | ofer zeitouni | timeline score: 11 | |
| Jul 15, 2014 at 19:18 | comment | added | Alex R. | Using the known TSP bound that John Gunnar Carlsson mentioned, one can probably get a heuristic bound by first asking what the typical size is of the smallest square that countains $\sqrt{n}$ points in the unit square. | |
| Jul 15, 2014 at 18:08 | comment | added | John Gunnar Carlsson | The quantity you're interested in is certainly bounded, because the length of the shortest path through all $n$ points (i.e. the TSP tour) has a length that is bounded by $\sqrt{2n} + 1.75$, as proven in [1], which we can approximate as simply $\sqrt{2n}$ since $n$ is large. If you take this tour and break it into segments consisting of $\sqrt{n}$ points each, you know that one of those segments has length of at most $\sqrt{2}$. [1] Few, L. "The shortest path and the shortest road through n points." Mathematika 2.02 (1955): 141-144. | |
| Jul 15, 2014 at 15:30 | history | edited | Ricardo Andrade |
replaced deprecated tag 'geometry'
|
|
| Jul 15, 2014 at 6:57 | comment | added | The Masked Avenger | Hmm. Maybe asking c greater than 1/2 is ambitious. I still think it should converge for c=1/2. | |
| Jul 15, 2014 at 6:50 | comment | added | The Masked Avenger | I think it should decrease, even if it were n^c many points rounded up, for fixed positive c less than 1. Set d to satisfy 2d +c=1, and consider a kxk square partition for k = floor(n^d). One of those pieces will have n^c points in it, and the length of the path should be O(n^-d), or some appropriate power. | |
| Jul 15, 2014 at 6:23 | history | edited | Kellar | CC BY-SA 3.0 |
added 25 characters in body
|
| Jul 15, 2014 at 6:05 | review | First posts | |||
| Jul 15, 2014 at 6:51 | |||||
| Jul 15, 2014 at 6:05 | history | asked | Kellar | CC BY-SA 3.0 |