Skip to content

Closest pair: analysis and higher dimensions

Scope

  • Slides: pp. 320-321
  • Major topic folder: proximity
  • Recording files touching this material: CS 564 - 03.13 15.2.txt, CS 564 - 03.25 16.1.txt, Mar 13, 2.34 PM​.txt
  • Goal of this file: You should be able to study this topic without reopening the slide deck.

Big picture

This final in-scope page closes the recurrence and points forward to higher dimensions. The key fact is that the algorithm matches the lower bound.

What you must know cold

  • Recurrence T(N) = 2T(N/2) + O(N) after presorting / stable maintenance.
  • Solution T(N) = O(N log N).
  • Idea of higher-dimensional extension via sparsity/packing.

Core ideas and reasoning

  • Since the merge is linear and the recursion is balanced, the Master-Theorem style solution is O(N log N).
  • Combined with the Ω(N log N) lower bound, closest pair is θ(N log N) in 2D.

Slide-by-slide digestion

p. 320 - Analysis

  • Let T(N) be the running time of the algorithm on N points.
  • The steps of CPAIR2 require:
    1. O(N)
    1. 2T(N/2)
    1. O(1)
    1. O(N)
    1. O(N)
    1. O(1)
  • Thus, T(N) = 2T(N/2) + O(N) ∈O(N log N).
  • The presort of S on y coordinate also requires O(N log N) time.

p. 321 - Preparata p. 199-204 discusses solving CLOSEST PAIR using a

  • divide-and-conquer algorithm for d > 3.
  • The approach depends on the notion of sparsity,
  • a measure of how many points can be in a d-dimensional
  • hypercube with sides that measure 2.
  • We made use of sparsity in the d = 1 and d = 2 case.
  • The result is that the closest pair of points in a set of N points
  • in Ed can be found in θ(N log N) time.
  • Proximity
  • Closest pair, divide-and-conquer

What you must be able to say or do in an exam

  • State the claim precisely before giving the argument.
  • Identify the known lower bound / recurrence / invariant you are using.
  • Keep the direction of the argument correct.
  • End with the exact asymptotic conclusion.

Complexity and performance facts

2D closest pair is optimal at θ(N log N).

Common mistakes and danger points

  • Do not forget that maintaining y-order efficiently is part of the full argument.
  • Higher-dimensional extensions keep the same divide-and-conquer spirit but the packing constant changes.

Professor emphasis from recordings

These points are distilled from the related recordings and focus on what the professor slowed down for, warned about, or connected to homework/exam reasoning.

  • The concluding point is that the recurrence solves to O(N log N) because the merge is linear; if you lose that fact, the whole optimality story collapses.
  • You should also be ready to state how the dimension changes the constant/packing argument instead of pretending 2D and higher dimensions are identical.

Exam-style drills and answer skeletons

Proof drill

Question. Explain the main argument in closest pair: analysis and higher dimensions in a logically correct order.

How to answer. Do not jump from intuition to conclusion. State the reduction/invariant/recurrence first, then derive the claimed bound.

Recap

What you must know cold

  • Recurrence T(N) = 2T(N/2) + O(N) after presorting / stable maintenance.
  • Solution T(N) = O(N log N).
  • Idea of higher-dimensional extension via sparsity/packing.

Core test / key idea

  • Since the merge is linear and the recursion is balanced, the Master-Theorem style solution is O(N log N).
  • Combined with the Ω(N log N) lower bound, closest pair is θ(N log N) in 2D.

Complexity

  • 2D closest pair is optimal at θ(N log N).

Common mistakes / danger points

  • Do not forget that maintaining y-order efficiently is part of the full argument.
  • Higher-dimensional extensions keep the same divide-and-conquer spirit but the packing constant changes.

Professor emphasis (from recordings)

  • The concluding point is that the recurrence solves to O(N log N) because the merge is linear; if you lose that fact, the whole optimality story collapses.
  • You should also be ready to state how the dimension changes the constant/packing argument instead of pretending 2D and higher dimensions are identical.

End-of-file summary

  • Recurrence T(N) = 2T(N/2) + O(N) after presorting / stable maintenance.
  • Solution T(N) = O(N log N).
  • Idea of higher-dimensional extension via sparsity/packing.
  • 2D closest pair is optimal at θ(N log N).
  • Do not forget that maintaining y-order efficiently is part of the full argument.
  • Higher-dimensional extensions keep the same divide-and-conquer spirit but the packing constant changes.
  • Previous file in reading order: Closest pair: 2D merge step
  • Source slide range: pp. 320-321 of comp_geometry_slides_new.pdf
  • Related recordings: CS 564 - 03.13 15.2.txt, CS 564 - 03.25 16.1.txt, Mar 13, 2.34 PM​.txt
  • Related homework-derived exam prompts included here: none directly mapped; generic exam drills added instead