CS341 Lecture Notes - Closest Pair Of Points Problem, Euclidean Distance, Subroutine

60 views12 pages

lemoncoyote675

16 Oct 2011

School

University of Waterloo

Department

Computer Science

Course

CS341

Professor

Forbes Burkowski

For unlimited access to Class Notes, a Class+ subscription is required.

Document Summary

We are given n points pi = (xi, yi), i = 1, , n. How far apart are the closest pair of points: we need the i and j values that minimize the. Y j )2: then return this distance. Brute force: compute distances for all n(n-1)/2 pairs and find the minimum: this algorithm runs in time q (n2). Closest pair by divide and conquer: sort by x-coordinate, then, divide: Find vertical line splitting points in half: conquer: Recursively find closest pairs in each half: combine: Check vertices near the border to see if any pair straddling the border is closer together than the minimum seen so far: our goal: Q (n) overhead so that the total run time is q (n log n). Let pl be points to the left of the dividing line. Let pr be points to the right of the dividing line. Find closest pair in pl: let d distance.

Related Questions

X. Write a da Subway system in which you define a new type Subway System A Subway Systemen of a private ArrayList lines. No methasoher than the constructed the addline method should modify this array list. Your class should have the following co-static methods (25 points) • Write a c tor Subway system that takes thing asing and initializes the private property lines to be an empty mysl • Write a method adine which takes as input a MetroLine newline and acknowline to the array lest lines. The mathed should retun void • Write a method got Distance Travelled which takes as in ArrayList path and returns a double representing the tual distance travelled or a paththalpos from the first Metrostation in the anaylist, to the Metrostation to the third til the cod of the array listHe cach Metrostation along the joy the calculate the distance between the Metrostation and the prices. If the ArrayList Metrostation path is less than 2 vales, y mesh shox return On You may the wale path issul For m e, if the ArrayList Metrostation path five Metrostation you code calculate the sum of the distance between the fin d ing the second third the third and fourth, and lastly the fourth and final stations. Hint: To calculate the distance between two points, you can use a method defined in the appendix in the Maputilities class . Write a method findNearest Station which takes as input a double x and a double y ad the Metrostation which is nearest to the x and y. To do this, it should leather all the Metrostations of all the Metrotines inside of this lines and find the Metro Station that is the smallest distance away. You can use the same appendix method as in the precis i on You may assume that there is a leadine MetroLine defined in the property lines. You may also assume that every MetroLine in lines has at least one Metrostation in Hint There is no method such as getAll Station defined a Metrotine ohjeet. This is since providing this method would rewal a lot about the implementation of the Metrolines and would differ depending on the kind of collectice you are using to store it. However, you can simulate this art of method by using the get PirstStop () and get Next Stop () methods to access every entry of the AmyList. Remember the condition that will cause getNext Stop (to be null • A method qet Neighboringstations which takes input a Metrostation station and re- turns an ArrayList The Arrayut Metrostation whild consist of all nephring stations to station possibly many if the station in ce may lines). P erample, if statice is the 3rd stop on the blue line, the 6th stop on the red line, and the stop on the green line, then the mothed should return an ArrayList

CS341 Lecture Notes - Closest Pair Of Points Problem, Euclidean Distance, Subroutine

Document Summary

Get access

Related Documents

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

CSCB36H3 Study Guide - Quiz Guide: Proof By Exhaustion, Complexity Class, Postcondition

CSCB36H3 Study Guide - Quiz Guide: Proof By Exhaustion, Complexity Class, Postcondition

Related Questions