Description
Write a data type to represent a set of points in the unit square (all points have x- and y-coordinates between 0 and 1) using a 2d-tree to support efficient range search (find all of the points contained in a query rectangle) and nearest-neighbor search (find a closest point to a query point). 2d-trees have numerous applications, ranging from classifying astronomical objects to computer animation to speeding up neural networks to mining data to image retrieval.
Geometric primitives. To get started, use the following geometric primitives for points and axis-aligned rectangles in the plane.
The immutable data type Point2D (part of algs4.jar) represents points in the plane. Here is the subset of its API that you may use:public class Point2D implements Comparable