Timeline for Finding closest point to a set of circles
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 21, 2014 at 16:23 | history | edited | user25199 | CC BY-SA 3.0 |
deleted 13 characters in body
|
| Mar 21, 2014 at 16:21 | comment | added | user25199 | @Douglas I answer the question about integer optimization. As I pointed out in the comment, if the minimum lies on one circle, it is equivalent to Alhazen's problem, famous in antiquity because it is higher degree than quadratic. To find the exact solution, one needs to enumerate all Fermat and anti-Fermat points plus Alhazen points, and decide which is optimal - certainly feasible and exact as you say, valuable but not as simple. I will delete the offending word and retain the upvote on your answer. | |
| Mar 21, 2014 at 15:49 | comment | added | Douglas Zare | Please delete the comment disparaging my answer or give an accurate criticism. I don't think you need to misrepresent my answer to give your own. | |
| Mar 21, 2014 at 15:45 | comment | added | Douglas Zare | I don't understand why an iterative numerical approach is better than an algebraic solution which shows that critical points which were a priori of high degree are actually quadratic and on a short fixed list. | |
| Mar 21, 2014 at 15:34 | comment | added | Douglas Zare | Why do you say my answer "eventually" gives exact solutions? It doesn't take long to find the intersection of circles. It's just the quadratic formula. Finding the solutions on the circles can be done algebraically or with Newton's method which converges rapidly. Your approach is the one that takes a significant amount of computational time, not mine. | |
| Mar 21, 2014 at 10:57 | comment | added | Joseph O'Rourke | (I used Mathematica to create the example below.) | |
| Mar 21, 2014 at 10:23 | comment | added | user25199 | @user3098199 I added some text - you can easily code the problem in mathematica to use these in-built routines, or use the ideas to develop your own code. Of course nonlinear optimization is a hard problem, so it is rare that you can be sure of getting the global minimum. | |
| Mar 21, 2014 at 10:20 | history | edited | user25199 | CC BY-SA 3.0 |
Further explanation, this time of the second point.
|
| Mar 21, 2014 at 10:10 | comment | added | user3098199 | Thanks for elaborate edit! Can you provide link for approach 2 which has details of how to solve similar problems? In the link you provided, the details are very minimal, am having a hard time figuring out how its related to this problem | |
| Mar 21, 2014 at 10:09 | vote | accept | user3098199 | ||
| Mar 21, 2014 at 9:56 | comment | added | user25199 | @user3098199 Elaborated as requested... | |
| Mar 21, 2014 at 9:55 | history | edited | user25199 | CC BY-SA 3.0 |
Expanded in response to request in comments.
|
| Mar 21, 2014 at 9:31 | comment | added | user3098199 | thanks for your answers. I would like to understand the first approach that you mentioned further. You have me for most of the approach, except for "t each step, divide the square into nine smaller squares by adding eight points around each point in the previous iteration, divide h by 3, compute the sum of distances for each new point, and remove points more than 32√h/2 above the minimum" Can you please elaborate this line further? | |
| Mar 21, 2014 at 7:38 | history | answered | user25199 | CC BY-SA 3.0 |