Java icon indicating copy to clipboard operation
Java copied to clipboard

Added RandomizedClosestPair code and test

Open Jivi-this-side opened this issue 6 months ago • 3 comments

  • [x] I have read CONTRIBUTING.md.
  • [x] This pull request is all my own work -- I have not plagiarized it.
  • [x] All filenames are in PascalCase.
  • [x] All functions and variable names follow Java naming conventions.
  • [x] All new algorithms have a URL in their comments that points to Wikipedia or other similar explanations.
  • [ ] All new code is formatted with clang-format -i --style=file path/to/your/file.java

Randomized Closest Pair of Points : (As per issue #6219 added this algo to repo)

The Closest Pair of Points problem finds the minimum Euclidean distance between two points in a 2D plane.

Randomized Algorithm Approach:

  • Randomly shuffle the input points.

  • Use a sweep-line + grid bucketing strategy to maintain only nearby points for efficient lookup.

  • Continuously update the closest pair distance while sweeping from left to right.

⚡ Time Complexity

  • Expected Time: O(n)

  • Worst-case Time: O(n log n)

Use Cases

  • Geospatial clustering

  • Nearest-neighbor search

  • Computational geometry in games, simulations, and robotics

Thank you!

Jivi-this-side avatar Apr 17 '25 14:04 Jivi-this-side