Skip to main content

Algorithms · Divide-and-conquer algorithms

Two disjoint color classes contain r ≥ 1 red and b ≥ 1 blue planar points

Problem

Algorithms practice problem

Two disjoint color classes contain r≥1r\ge1 red and b≥1b\ge1 blue planar points. Find a minimum-distance opposite-color pair, breaking ties lexicographically. Design an O((r+b)log⁡(r+b))O((r+b)\log(r+b))-time divide-and-conquer algorithm, prove the cross-partition candidate bound, and state auxiliary space.

Hint

Hint

** Same-color points can cluster, so the ordinary bichromatic strip argument needs a different sparse structure.

Check your work

Work the problem yourself first. Then open it in Training to check your answer and read the full worked solution.

The answer check and full solution for this problem come with ProofAnvil Practice membership ($19 USD monthly). See membership. Or start with the free Algorithms sample problem: Try the free sample problem.

More Algorithms practice problems

Back to Algorithms

An original ProofAnvil practice problem, written for this course. ProofAnvil is a practice course, not a homework-answer service.