Lesson plan

Proximity problems

Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects. A subset of these problems stated in terms of points only are sometimes referred to as closest point problems, although the term "closest point problem" is also used synonymously to the nearest neighbor search. A common trait for many of these problems is the possibility to establish the Θ(n log n) lower bound on their computational complexity by reduction from the element uniqueness problem basing on an observation that if there is an efficient algorithm to compute some kind of minimal distance for a set of objects, it is trivial to check whether this distance equals to 0.

Back to article

Article summary

Proximity problems is a class of problems in computational geometry which involve estimation of distances between geometric objects. A subset of these problems stated in terms of points only are sometimes referred to as closest point problems, although the term "closest point problem" is also used synonymously to the nearest neighbor search. A common trait for many of these problems is the possibility to establish the Θ(n log n) lower bound on their computational complexity by reduction from the element uniqueness problem basing on an observation that if there is an efficient algorithm to compute some kind of minimal distance for a set of objects, it is trivial to check whether this distance equals to 0.

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.