Uh oh!
There was an error while loading.Please reload this page.
- Notifications
You must be signed in to change notification settings - Fork1.9k
Update geometry/nearest_points.md, adding a randomized algorithm explanation#1473
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to ourterms of service andprivacy statement. We’ll occasionally send you account related emails.
Already on GitHub?Sign in to your account
Uh oh!
There was an error while loading.Please reload this page.
Conversation
Explanation of randomized algorithms for closest pair of points.
…orrect visualization
izanbf1803 commentedJun 26, 2025
@adamant-pwn Please someone check this PR! |
mhayter commentedJun 28, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Wow, this is a significant contribution !Thank you. I'll try to read this soon and give input. |
mhayter commentedJun 28, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Some of the math@jxu might be good at too in addition to@adamant-pwn. Briefly, the last expressions are not rendering properly. That might be a spacing issue: Lol it works in GitHub haha. |
Quick edits. Rendering
mhayter commentedJun 28, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Given the complexity, it may make sense to add basic tests to our suite. Personally, I'd prefer proofs to be in one of those drop downs as I'm not as mathematically inclined and am likely to skip over it unless I'm really interested. It's probably prudent to include the worst case time and scenarios in which they fail expectation. The math claims will likely require hours to really sit down and verify for me but I'm hoping some of the other guys can chime in. PS I'm not sure if we've standardized the site as American English or British English spellings ( I noticed practise vs practice.) |
izanbf1803 commentedJun 28, 2025 • edited
Loading Uh oh!
There was an error while loading.Please reload this page.
edited
Uh oh!
There was an error while loading.Please reload this page.
Thanks for the useful changes@mhayter !!! I think I fixed the issue with the equation, block equations need to be surrounded by newlines apparently. How could this thing of having a dropdown for the proof be implemented? (EDIT: done!) |
mhayter commentedJun 28, 2025
The current code does not compile: candidate_closest does not exist. Also, I'd consider accepting references in the dist function and also changing the name of dis generator as it looks very similar. |
Replace "cube" with "square"Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
Better formattingCo-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
mhayter commentedSep 27, 2025
Are there any other changes required?@adamant-pwn |
izanbf1803 commentedOct 7, 2025
Ping :) |
adamant-pwn left a comment
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others.Learn more.
Thank you for your patience! 🙏
I think the current version looks good, it should be ok to merge. Thanks a lot!
dfbbe2b intocp-algorithms:mainUh oh!
There was an error while loading.Please reload this page.
mhayter commentedOct 10, 2025
Congrats@izanbf1803 and@adamant-pwn ! |
izanbf1803 commentedOct 11, 2025
Thanks@mhayter and@adamant-pwn for helping me improve it! :) |
Uh oh!
There was an error while loading.Please reload this page.
The new explanation adds two randomized algorithms that have linear expected runtime. One of them being much simpler to implement and remember than the traditional divide and conquer algorithm, and improving its runtime efficiency. An implementation for the first one is provided. An image is included to clarify the strategy of the first randomized algorithm.