Timeline for How to find a closest integer point to the intersection of two lines?
Current License: CC BY-SA 4.0
34 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| S Jul 23 at 11:26 | history | suggested | Don Hatch | CC BY-SA 4.0 |
Previous edit introduced the misleading/confusing phrase "quadrant of the plane". Reverting that part to earlier clear phrasing.
|
| Jul 20 at 18:15 | review | Suggested edits | |||
| S Jul 23 at 11:26 | |||||
| Feb 12, 2021 at 8:56 | history | edited | P Shved | CC BY-SA 4.0 |
fixed my bad grammar
|
| Mar 3, 2019 at 21:28 | history | edited | P Shved | CC BY-SA 4.0 |
deleted 54 characters in body
|
| Dec 31, 2018 at 0:49 | comment | added | Joseph O'Rourke | A generalization: Sommer, Naftali, Meir Feder, and Ofir Shalvi. "Finding the closest lattice point by iterative slicing." SIAM Journal on Discrete Mathematics 23, no. 2 (2009): 715-731. ResearchGate link. | |
| May 23, 2017 at 12:37 | history | edited | CommunityBot |
replaced http://stackoverflow.com/ with https://stackoverflow.com/
|
|
| S May 19, 2016 at 23:37 | history | suggested | Don Hatch | CC BY-SA 3.0 |
replaced "normal and offset" with something more explicit, per feedback
|
| May 19, 2016 at 23:09 | comment | added | Don Hatch | @TonyK please see previous few comments, I couldn't cc more than one person at a time. | |
| May 19, 2016 at 23:08 | review | Suggested edits | |||
| S May 19, 2016 at 23:37 | |||||
| May 19, 2016 at 23:04 | comment | added | Don Hatch | @GerryMyerson Yes I know, I purposely put a space in the @ TonyK (and doing it again now) to denote my failed intent there. Frustrating. Okay, I thought "normal and offset" was clarifying, but I guess not. I'll replace it with something explicit like "Ax+By=C with A,B,C integers". That will make it more like the stackoverflow phrasing, which I found to be quite good and clear in this regard. | |
| May 19, 2016 at 22:44 | comment | added | Gerry Myerson | @Don, you can't ping two people in one comment. Also, I don't know what "normal and offset" means. | |
| May 19, 2016 at 20:56 | comment | added | Don Hatch | @GerhardPaseman and @ TonyK I edited the question to fix the problems we've been complaining about, and removed three of my previous comments about them. | |
| S May 19, 2016 at 19:59 | history | suggested | Don Hatch | CC BY-SA 3.0 |
fix 4 red herrings everyone has been complaining about
|
| May 19, 2016 at 19:49 | review | Suggested edits | |||
| S May 19, 2016 at 19:59 | |||||
| May 19, 2016 at 4:01 | comment | added | Don Hatch | I've posted a solid solution, which I implemented and tested exhaustively on small inputs (the original formulation, lines don't have to hit grid points) so I'm confident I didn't miss anything. The testing did reveal a bug in the case enumeration, easily fixed. @WadimZudilin yes, it's a version of EA. Now I'm trying to think of how to generate some killer test cases, that is, examples that wouldn't be solvable in one's lifetime using a naive implementation. Best I can think of is run the algorithm backwards, but I wonder if there's a clever simpler method for generating challenging examples. | |
| May 16, 2016 at 22:55 | answer | added | Don Hatch | timeline score: 2 | |
| Aug 17, 2013 at 12:44 | answer | added | Alexey Ustinov | timeline score: 2 | |
| Jul 31, 2013 at 20:41 | answer | added | anonymousnerd | timeline score: 1 | |
| Jun 15, 2011 at 21:23 | comment | added | Gerhard Paseman | It would be nice to be explicitly told that $(x',y')$ is also supposed to have integer coordinates (as opposed to rational or dyadic or whatever). Gerhard "Ask Me About System Design" Paseman, 2011.06.15 | |
| Apr 29, 2010 at 7:24 | answer | added | Robby McKilliam | timeline score: 17 | |
| Apr 29, 2010 at 0:46 | answer | added | Victor Miller | timeline score: 6 | |
| Apr 28, 2010 at 9:40 | comment | added | TonyK | @shvedsky, I didn't say it would be the closest one. I was just pointing out that your comment (which I quoted) makes no sense. | |
| Apr 28, 2010 at 6:47 | history | edited | Dylan Thurston |
edited tags
|
|
| Apr 28, 2010 at 6:16 | comment | added | Wadim Zudilin | In any case I would suggest to tag number theory as well. Because it really sounds like a version of the Euclidean algorithm. | |
| Apr 28, 2010 at 2:38 | comment | added | François G. Dorais | Gaussian lattice reduction probably works. | |
| Apr 27, 2010 at 21:14 | comment | added | P Shved | @TonyK, of course, we are guaranteed to find an integer point in such a way. But will it be the closest one? <br/> If you propose to check all points before it, then the number of iterations needed for such a walk is linear to multiplication of coefficients of normal vectors of lines. That renders such a solution exponential. | |
| Apr 27, 2010 at 21:11 | comment | added | TonyK | "The (x,y) point is seemingly needed just to make the problem NP-complete instead of NP-hard." No, you can find such an (x,y) easily. Just go far enough away from the point of intersection so that the vertical or horizontal distance between the two lines is >= 1. | |
| Apr 27, 2010 at 21:03 | answer | added | anonymous | timeline score: 1 | |
| Apr 27, 2010 at 21:02 | history | edited | P Shved | CC BY-SA 2.5 |
added 28 characters in body; added 1 characters in body; added 36 characters in body
|
| Apr 27, 2010 at 20:58 | comment | added | P Shved | I'm very sorry that I didn;t learn how to tag and paste TeX properly, and I hope that the community would be kind to do it for me... :-/ | |
| Apr 27, 2010 at 20:53 | comment | added | P Shved | @Quaochu, in the length of input - i.e. sum of logarithms of the integers that define each line (normal vectors, with GCD equal to one, for simplicity; and one integer point it crosses), and coordinates of (x,y). | |
| Apr 27, 2010 at 20:51 | comment | added | Qiaochu Yuan | Polynomial in what? | |
| Apr 27, 2010 at 20:43 | history | edited | P Shved | CC BY-SA 2.5 |
added 3 characters in body
|
| Apr 27, 2010 at 20:38 | history | asked | P Shved | CC BY-SA 2.5 |