Sets of Two-Dimensional Points (point_set)

Definition

An instance S of the parameterized data type point_set<I> is a collection of items (ps_item). Every item in S contains a two-dimensional point as key (data type point), and an information from data type I, called the information type of S. The number of items in S is called the size of S. A point set of size zero is said to be empty. We use <p,i> to denote the item with point p, and information i. For each point p there is at most one item <p,i> in S. Beside the normal dictionary operations, the data type point_set provides operations for rectangular range queries and nearest neighbor queries.

Creation

point_set<I>	S;	creates an instance S of type point_set<I> and initializes S to the empty set.

Operations

point	S.key(ps_item it)	returns the point of item it. Precondition: it is an item in S.
I	S.inf(ps_item it)	returns the information of item it. Precondition: it is an item in S.
ps_item	S.insert(point p, I i)	associates the information i with point p. If there is an item <p,j> in S then j is replaced by i, else a new item <p,i> is added to S. In both cases the item is returned.
ps_item	S.lookup(point p)	returns the item with point p (nil if no such item exists in S).
ps_item	S.nearest_neighbor(point q)
		returns the item <p,i> in S such that the distance between p and q is minimal.
list<ps_item>	S.range_search(double x0, double x1, double y0, double y1)
		returns all items <p,i> in S with x_0 <= p.xcoord() <= x_1 and y_0 <= p.ycoord() <= y_1.
void	S.del(point p)	deletes the item with point p from S.
void	S.del_item(ps_item it)	removes item it from S. Precondition: it is an item in S.
void	S.change_inf(ps_item it, I i)
		makes i the information of item it. Precondition: it is an item in S.
list<ps_item>	S.all_items()	returns the list of all items in S.
list<point>	S.all_points()	returns the list of all points in S.
void	S.clear()	makes S the empty point_set.
bool	S.empty()	returns true iff S is empty.
int	S.size()	returns the size of S.

Implementation

Point sets are implemented by a combination of two-dimensional range trees [79,51] and Voronoi diagrams. Operations insert, lookup, del_item, del take time O(log^2 n), key, inf, empty, size, change_inf take time O(1), and clear takes time O(nlog n). A range_search operation takes time O(k+log^2 n), where k is the size of the returned list. A nearest_neighbor query takes time O(n). Here n is the current size of the point set. The space requirement is O(nlog n).