Timeline for Efficient way to generate random points with a predefined lower bound on their pairwise Euclidean distance
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 26, 2014 at 18:49 | answer | added | Mark Adler | timeline score: 8 | |
| Feb 19, 2014 at 22:31 | history | edited | Szabolcs | edited tags | |
| Mar 19, 2012 at 11:10 | vote | accept | PlatoManiac | ||
| Mar 6, 2012 at 16:22 | answer | added | Daniel Lichtblau | timeline score: 8 | |
| Mar 6, 2012 at 10:30 | history | edited | PlatoManiac | CC BY-SA 3.0 | Changed the title to make it mpre precise |
| Mar 6, 2012 at 8:51 | answer | added | kglr | timeline score: 6 | |
| Mar 6, 2012 at 0:24 | answer | added | Heike | timeline score: 13 | |
| Mar 5, 2012 at 21:03 | history | tweeted | twitter.com/#!/StackMma/status/176774888021958656 | ||
| Mar 5, 2012 at 21:02 | comment | added | whuber | For practical solutions which may meet your needs, start with the Wikipedia article on low-discrepancy sequences and then look closely at the Halton sequence. | |
| Mar 5, 2012 at 20:39 | answer | added | Archimedes of Syracuse | timeline score: 21 | |
| Mar 5, 2012 at 20:11 | comment | added | whuber | I would like to suggest you do have a requirement on the distribution. Otherwise, find two children and ask them to draw pictures of solutions. Check the solutions and digitize them. Ask Mathematica to choose randomly between the two solutions. After the initial computation of the two solutions, this is extremely efficient and is obviously random. I'm not being facetious: this is a nice example of a spatial stochastic process that meets every one of your stated requirements. It might help you see why specifying a distribution is important. | |
| Mar 5, 2012 at 19:32 | answer | added | Andy Ross | timeline score: 36 | |
| Mar 5, 2012 at 19:26 | comment | added | PlatoManiac | @whuber I dont have any special requirement on the distribution any probability distribution should do. You can have a look at the commented part of the code where I use NormalDistribution. There the variance use used as DistanceBound and mean of the lower and upper bound is chosen as the mean of the distribution. One can use multiple of the DistanceBound variance to guarantee too many iterations are not needed to achieve the requested sample. If you know any efficient solution please share. | |
| Mar 5, 2012 at 18:22 | comment | added | whuber | "Random" does not mean merely arbitrary; nor, in practice, does it mean (merely) that random numbers were involved. To use "random" points, you need to know their probability distribution. (There exist efficient solutions to this problem having very different distributions.) So: precisely what distribution do you want these points to have? | |
| Mar 5, 2012 at 17:42 | answer | added | Yves Klett | timeline score: 15 | |
| Mar 5, 2012 at 17:20 | comment | added | PlatoManiac | @kguler Thx for the comment! I corrected my post. | |
| Mar 5, 2012 at 17:20 | history | edited | PlatoManiac | CC BY-SA 3.0 | added 3 characters in body |
| Mar 5, 2012 at 17:18 | comment | added | kglr | You probably meant .. so that NO two points ... has a Euclidean distance lower than say d in the second line? | |
| Mar 5, 2012 at 17:18 | comment | added | PlatoManiac | @YvesKlett The elements $p_1$ and $p_2$ are not sequential in the list that we want to generate. They are just arbitrary pair. | |
| Mar 5, 2012 at 17:12 | comment | added | Yves Klett | Perhaps I am getting this backwards, but why not generate random points within a given envelope (say, a circle) and scale the random coordinates with the largest possible distance within that envelope (e.g. the diameter) to your parameter d? Or are p1 and p2 sequential elements of the list? | |
| Mar 5, 2012 at 17:11 | history | edited | PlatoManiac | CC BY-SA 3.0 | added 12 characters in body |
| S Mar 5, 2012 at 16:59 | history | suggested | Andrew | CC BY-SA 3.0 | title spelling |
| Mar 5, 2012 at 16:53 | review | Suggested edits | |||
| S Mar 5, 2012 at 16:59 | |||||
| Mar 5, 2012 at 16:47 | history | asked | PlatoManiac | CC BY-SA 3.0 |