CISC 365 Lecture Notes - Lecture 9: Daihatsu Delta, Merge Sort, If And Only If

20 views6 pages

Document Summary

Another surprising and satisfying application of the d&c method is the following algorithm for nding the closest pair of points in a set of points in the x-y plane. Assume we have n points, each identi ed by its x and y coordinates. Our goal is to nd the two points with the minimum distance. Obviously we can solve this problem in o (n^2) time by computing the distance between all pairs of points. It may seem unlikely that we can reduce this, but by clever design we can eliminate enough of the pairwise distance calculations that we can achieve a lower complexity. For reasons that will become clear later, we start by creating a list of all the points sorted by their x-coordinate (x-list) and another list of all the points sorted by their y-coordinate (y-list). This is a pre-processing phase that sets up the rest of the algorithm.

Get access

Grade+
$40 USD/m
Billed monthly
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
10 Verified Answers
Class+
$30 USD/m
Billed monthly
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
7 Verified Answers

Related Documents

Related Questions