The Closest Starbucks Problem: Space Dividing Data Structures

Data Structures

Implementation of a space-partitioning data structure in order to solve the nearest neighbor problem.

Given a static list of points, the student must design a data structure supporting an efficient nearest-neighbor search; points are awarded based on correctness and efficiency. Students are encouraged to use a kd-tree, giving them experience in working with binary search trees and dealing with problems within the area of computational geometry.

Duration: 2 weeks

Background: Students are assumed to have 2.5 semesters of programming experience, including at least half a semester of C++, and to have had exposure to the concept of binary search trees. kd-trees are not covered in the assignment; instructors should consider discussing them in class before students begin.

John Karro, William Brinkman

code, run-time analysis

Two Weeks

reading

Implementation, Recursion, trees/heaps, selection of algorithm and data structures

Workplace Scenario:
You have been hired to design a new Starbucks locator smart phone app. The app will download with a list of U.S. Starbucks locations. When activated, the app will be provide with the coordinates by the device GPS, and locate the closest Starbucks to the current position (which it can then feed to a map app that will be in charge of calculating the route). Your problem is to figure out how to maintain the list in such a way that it can be quickly queried. You could just scan the full list – but given the size of the list, and the user’s speed expectations, that isn’t going to make for a happy client. You need to do better for that.

On the bright side: you can consider the list static. New Starbucks do not open all that often. So your data structure does not need to support an insert data structure. (When there is an update, you can just reconstruct the entire data structure from the modified list during down time.) So you priority is the query runtime. The user need to find the closest Starbuck’s as fast as possible – the user needs coffee now!!!


Importance: In this you will gain experience with dictionary data structures by designing and implementing a data structure that support fast “nearest neighbor” queries. The ideal data structure for the assignment is a space-dividing structure such as the kd-tree; implementations based on this will be considerably faster than any alternative without sacrificing on precision. There are, however, many alternatives – students unable to implement such a structure will be able to make use of simpler structure, at a significant loss of time and/or precision (and, hence, length).

N/A