# bpr/kd_tree

### Subversion checkout URL

You can clone with
or
.
OCaml implementation of kd tree data structure and algorithms
OCaml

Fetching latest commit…

Cannot retrieve the latest commit at this time

 Failed to load latest commit information. OMakefile OMakeroot README.md kd_tree.ml multidim.ml repl.ml spaces.ml two_d.ml usa_cities.csv

# KD Trees

## Introduction

The k-d tree is a binary tree in which every node is a k-dimensional point. Every non-leaf node can be thought of as implicitly generating a splitting hyperplane that divides the space into two parts, known as subspaces. Points to the left of this hyperplane represent the left sub-tree of that node and points right of the hyperplane are represented by the right sub-tree. The hyperplane direction is chosen in the following way: every node in the tree is associated with one of the k-dimensions, with the hyperplane perpendicular to that dimension's axis. So, for example, if for a particular split the "x" axis is chosen, all points in the subtree with a smaller "x" value than the node will appear in the left subtree and all points with larger "x" value will be in the right sub tree. In such a case, the hyperplane would be set by the x-value of the point, and its normal would be the unit x-axis.[1]

## Algorithm

The algorithm was inspired by the Wikipedia entry and by Overmars computational geometry book.

Implementation: multidim.ml spaces.ml kd_tree.ml

Usage:

• Compile with omake.
• Run './repl -input_file usa_cities.csv'
• In the repl, enter lat and long separated by comma, e.g.

enter (lat,long) >>> -121.46,38.52
{name=Parkway-South Sacramento; population=40797; state=California; latlong=(-121.45,38.51)}

Todo:

• Fix range search
• Implement algorithm in Scala, Clojure, and Haskell
Something went wrong with that request. Please try again.