Movatterモバイル変換


[0]ホーム

URL:


Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

Sign up
Appearance settings

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

Merged
adamant-pwn merged 24 commits intocp-algorithms:mainfromizanbf1803:master
Oct 7, 2025

Conversation

@izanbf1803
Copy link
Contributor

@izanbf1803izanbf1803 commentedJun 24, 2025
edited
Loading

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.

Explanation of randomized algorithms for closest pair of points.
@izanbf1803
Copy link
ContributorAuthor

@adamant-pwn Please someone check this PR!

@mhayter
Copy link
Contributor

mhayter commentedJun 28, 2025
edited
Loading

Wow, this is a significant contribution !Thank you. I'll try to read this soon and give input.

@mhayter
Copy link
Contributor

mhayter commentedJun 28, 2025
edited
Loading

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:

$$O(n + \sum_{i=1}^{n} i \Pr(X_i = 1)) \le O(n + \sum_{i=1}^{n} i \frac{2}{i}) = O(3n) = O(n) \quad \quad \blacksquare $$

Lol it works in GitHub haha.

Quick edits. Rendering
@mhayter
Copy link
Contributor

mhayter commentedJun 28, 2025
edited
Loading

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
Copy link
ContributorAuthor

izanbf1803 commentedJun 28, 2025
edited
Loading

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 reacted with thumbs up emoji

@mhayter
Copy link
Contributor

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.

izanbf1803and others added2 commitsAugust 23, 2025 15:27
Replace "cube" with "square"Co-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
Better formattingCo-authored-by: Oleksandr Kulkov <adamant.pwn@gmail.com>
@mhayter
Copy link
Contributor

Are there any other changes required?@adamant-pwn

@izanbf1803
Copy link
ContributorAuthor

Ping :)

Copy link
Member

@adamant-pwnadamant-pwn left a 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!

izanbf1803 and mhayter reacted with heart emoji
@adamant-pwnadamant-pwn merged commitdfbbe2b intocp-algorithms:mainOct 7, 2025
3 checks passed
github-actionsbot added a commit that referenced this pull requestOct 7, 2025
@mhayter
Copy link
Contributor

Congrats@izanbf1803 and@adamant-pwn !

@izanbf1803
Copy link
ContributorAuthor

Thanks@mhayter and@adamant-pwn for helping me improve it! :)

mhayter reacted with thumbs up emoji

Sign up for freeto join this conversation on GitHub. Already have an account?Sign in to comment

Reviewers

@adamant-pwnadamant-pwnadamant-pwn approved these changes

Assignees

No one assigned

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@izanbf1803@mhayter@adamant-pwn

[8]ページ先頭

©2009-2025 Movatter.jp