Timeline for Find m most distant points from a set of n points [closed]
Current License: CC BY-SA 3.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 15, 2019 at 20:46 | comment | added | John Shedletsky | Came here for a solution to this exact problem and it is annoying that it is closed because a couple of people couldn't understand the question, which I think is quite clear. | |
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| Dec 6, 2014 at 11:57 | comment | added | Manfred Weis | @difftator here the promised binary programming formulation: introduce binary variables $v_i$ for the selecting a point itself and $e_{ij}$ for selecting the pair $v_i$ and $v_j$ of points and, let further $w_{ij}$ denote the entries of the distance table. The objective is then to maximize the sum over all $w_{ij}e_{ij}$ under the constraints, that $e_{ij}\le v_i, e_{ij}\le v_j,\Sigma v_i = m, \Sigma e_{ij} = m^2$. In the relaxed version the additional constraint $e_{ij}\ge v_i+v_j-1$ further reduces the integrality gap. I hope that helps in utilizing existing LP solvers for your problem. | |
| Dec 5, 2014 at 18:27 | comment | added | difftator | @ManfredWeis any suggestions would be welcome. Thanks! | |
| Dec 5, 2014 at 18:14 | comment | added | Manfred Weis | @difftator you don't need quadratic binary programming; linear binary programming is sufficient. If you need assistance in the formulation, let me know. Also a relaxed, i.e. ordinary linear programming formulation is possible of which the solution may be a good approximation of the exact solution. | |
| Dec 5, 2014 at 17:59 | comment | added | difftator | @ManfredWeis I have just found a better reference for solving Binary Quadratic Programming problems "Solving Large Scale Binary Quadratic Problems:Spectral Methods vs. Semidefinite Programming" It seems that O(n^3) solutions exist (Eigenvalues) that fits nicely with large n and can be easily implemented with a standard linear algebra package. So I think I will pursue that solution. | |
| Dec 5, 2014 at 16:07 | comment | added | Hugh Thomas | An alternative to the strategy the OP proposes would be to find the minimal distance between a pair of points in the set, and discard one of those points, and repeat until only m points remain. The time would be quadratic, but I guess the outcome would be better than with the algorithm the OP proposes. | |
| Dec 5, 2014 at 13:34 | comment | added | Manfred Weis | I vote to put the question off hold as (at least to me) it is clear that an efficient heuristic for finding a maximum-weight m-clique in a complete graph, whose edge-weights resemble (euclidean) distances, is sought. As the problem can be interpreted differently (e.g. Computational Geometry, or Graph Theory), it would be interesting to see the exact algorithms or heuristics found on ground of those interpretations. | |
| Dec 5, 2014 at 13:24 | comment | added | Manfred Weis | @difftator I believe that your problem is NP-hard, but it can be formulated as a binary linear programming problem; unfortunately the question has been put on hold, which is a pitty because I see several interesting aspects to it. Maybe you should only state the problem and ask for solutions or heuristics and, do not mention what you have tried so far. | |
| Dec 5, 2014 at 13:12 | history | closed |
Stefan Kohl♦ Ryan Budney Steven Landsburg Stefan Waldmann Jeremy Rouse |
Needs details or clarity | |
| Dec 5, 2014 at 2:27 | comment | added | difftator | Thanks @JosephO'Rourke I thought this too, but consider a set of $n$ > $3$ points on a line where you are seeking the $n$ > $m$ >= $3$ subset that are maximally distant. | |
| Dec 5, 2014 at 2:21 | comment | added | Joseph O'Rourke | I think perhaps you should just compute the convex hull of your $n$ points, and then select $m$ of the hull points. I suggest this without really understanding what you are seeking. :-) | |
| Dec 5, 2014 at 2:16 | history | edited | difftator | CC BY-SA 3.0 |
added 187 characters in body
|
| Dec 5, 2014 at 1:59 | history | edited | difftator | CC BY-SA 3.0 |
added 187 characters in body
|
| Dec 5, 2014 at 1:54 | comment | added | difftator | Hi @HughThomas, thanks for replying. Here is a link to the kd-tree (en.wikipedia.org/wiki/K-d_tree) | |
| Dec 5, 2014 at 1:51 | history | edited | difftator | CC BY-SA 3.0 |
added 187 characters in body
|
| Dec 5, 2014 at 1:45 | comment | added | Hugh Thomas | This question uses a lot of terms which are unfamiliar to me and which I think might also be unfamiliar to other people in this forum who might still be interested in this question (as I am). What is SE(3)? What is a kd-tree? What is 6-DOF? You also still haven't said what you want to maximize: is it the minimum over all pairs of the pairwise distances among your points, or some other function of the distances? | |
| Dec 5, 2014 at 1:33 | comment | added | difftator | I have amended the question to reflect you comments - thanks! | |
| Dec 5, 2014 at 1:32 | history | edited | difftator | CC BY-SA 3.0 |
added 340 characters in body
|
| Dec 5, 2014 at 1:28 | comment | added | difftator | @JosephO'Rourke thanks for amending the tag - I am new on this forum and was influenced by existing implementation which is using the kd-tree | |
| Dec 5, 2014 at 1:27 | comment | added | difftator | @GerryMyerson to clarify your question - you are right m > 1 | |
| Dec 5, 2014 at 0:55 | comment | added | Joseph O'Rourke | No doubt the graph-theory mis-tagging results from the OP's idea of using a $kd$-tree. It should be tagged metric-geometry and discrete-geometry. I have so edited. | |
| Dec 5, 2014 at 0:54 | history | edited | Joseph O'Rourke |
edited tags
|
|
| Dec 5, 2014 at 0:52 | comment | added | Joseph O'Rourke | How large is $d$? This can affect the best choice. | |
| S Dec 4, 2014 at 23:52 | history | suggested | jeq | CC BY-SA 3.0 |
Added line-breaks to the description of the algorithm
|
| Dec 4, 2014 at 23:32 | review | Suggested edits | |||
| S Dec 4, 2014 at 23:52 | |||||
| Dec 4, 2014 at 23:05 | review | Close votes | |||
| Dec 5, 2014 at 13:12 | |||||
| Dec 4, 2014 at 22:41 | comment | added | Brendan McKay | Why did you classify it as graph theory when your question doesn't mention a graph? | |
| Dec 4, 2014 at 22:41 | comment | added | Gerry Myerson | It's not even clear to me what this means in the case $m=1$. Would you want the point whose closest point is farthest away? the point whose farthest point is farthest away? the point farthest away from the average of the other points? | |
| Dec 4, 2014 at 22:33 | comment | added | Alex Degtyarev | What is "maximally distant"? What exactly is to be maximized? | |
| Dec 4, 2014 at 22:32 | review | First posts | |||
| Dec 4, 2014 at 22:33 | |||||
| Dec 4, 2014 at 22:29 | history | asked | difftator | CC BY-SA 3.0 |