Assignment 7: k-d Tree

Objectives

to implement a variant of binary search trees

Introduction

We have already analyzed GPS tracks so that we can detect when fishing vessels have been stationary for suspiciously long times in protected waters. Another challenge of tracking illegal fishing is that fishing vessels may offload their catch into other vessels that have not been in protected areas in order to hide where a catch was made. For this assignment we will implement an ADT to maintain a collection of geographic coordinates so that we could, as we update the location of the vessels we are tracking, determine which other vessels are nearby that may be involved in offloading.

Assignment

Complete the implementation of the functions described in kdtree.h from the /c/cs223/hw7/Required/ directory. The functions define a Set-of-Points ADT with the ability to find points that are with a certain range. Note that none of the functions need to implement any coordinate normalization: it is the responsibility of the user to ensure that, for example, all longitudes are in the range -180 (exclusive) to 180 (inclusive); the ADT will treat two points at the same latitude with one at longitude -180 and one at longitude 180 as different points.

The functions should run in the following worst-case time bounds.

kdtree_create: $O(n \log n)$
kdtree_add: $O(\log n)$
kdtree_contains: $O(\log n)$
kdtree_remove: $O(\sqrt{n})$
kdtree_range: $O(\sqrt{n} + p)$ where $p$ is the number of points in the range
kdtree_range_for_each: $O(\sqrt{n} + p)$ where $p$ is the number of points in the range, and assuming that f runs in $O(1)$ time
kdtree_destroy: $O(n)$

Where $n$ is the number of points in the set, and the bounds apply only then the set is balanced; otherwise the bounds are $O(n)$ (except for kdtree_create, which must always run in $O(n \log n)$ time). All time bounds assume that malloc and free run in $O(1)$ time.

Your implementation should work with the main function in kdtree_unit.c also found in /c/cs223/hw7/Required/ along the location library. There is a makefile in /c/cs223/hw7/Optional that builds an executable called Unit. The Unit executable runs a number of different unit tests and you can select one by passing its index on the command line. See the code for the unit tests for more details about each one.

Example

[jrg94@rattlesnake ~]$ for N in 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15; do echo === TEST $N ===; ./Unit $N | sort -n; done
=== TEST 1 ===
PASSED
=== TEST 2 ===
PASSED
=== TEST 3 ===
PASSED
=== TEST 4 ===
PASSED
=== TEST 5 ===
PASSED
=== TEST 6 ===
15.071 -163.957
15.357 -157.807
16.698 -164.924
17.079 -162.024
18.085 -162.655
18.863 -163.994
19.097 -160.178
19.353 -162.740
19.712 -161.068
20.376 -162.999
21.833 -161.960
22.189 -157.489
22.215 -158.356
22.589 -157.028
22.858 -158.387
22.998 -156.598
23.420 -162.370
23.858 -157.537
24.797 -157.050
24.904 -164.680
=== TEST 7 ===
22.189 -157.489
22.589 -157.028
=== TEST 8 ===
15.07 -163.96
15.36 -157.81
16.70 -164.92
17.08 -162.02
18.08 -162.65
18.86 -163.99
19.10 -160.18
19.35 -162.74
19.71 -161.07
20.38 -163.00
21.83 -161.96
22.19 -157.49
22.21 -158.36
22.59 -157.03
22.86 -158.39
23.00 -156.60
23.42 -162.37
23.86 -157.54
24.80 -157.05
24.90 -164.68
=== TEST 9 ===
22.19 -157.49
22.59 -157.03
=== TEST 10 ===
=== TEST 11 ===
22.000 -157.000
22.000 -158.000
22.189 -157.489
22.589 -157.028
23.000 -157.000
23.000 -158.000
=== TEST 12 ===
PASSED
=== TEST 13 ===
PASSED
=== TEST 14 ===
PASSED
=== TEST 15 ===
PASSED

Submissions

Submit your source code necessary to build the executable using the provided makefile and supporting code. There is no need to submit the provided makefile, location library, kdtree_unit.c, or kdtree.h. Your makefile can assume that those supporting files have been copied into the current directory, but should not assume they are still in their original locations.