Skip to content

Randomized O(n) Closest pair of points #1386

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.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom
Open
izanbf1803 opened this issue Oct 30, 2024 · 1 comment
Open

Randomized O(n) Closest pair of points #1386

izanbf1803 opened this issue Oct 30, 2024 · 1 comment

Comments

@izanbf1803
Copy link
Contributor

In the article "Finding the nearest pair of points", I think it would be nice to add this alternative solution of using a randomized algorithm, which is linear (in expectation and with high probability), simpler to implement properly and introduces the idea of randomized algorithms. I'd like to write it myself.

Do you think it would be nice to include other practical randomized algorithms? Since I am studing these now, I could try to find other articles to improve with randomized algorithms.
@jxu
Copy link
Contributor

jxu commented Nov 4, 2024

Sure. The only randomized algorithms I know of are for primality testing, where it is random but guaranteed with high probability the result will be correct. I guess the simulated annealing article falls under that too #1371, although I have never used it for a problem that couldn't be solved deterministically. It might be used in quicksort too.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@jxu @izanbf1803