\manpage {point\_set} {I} {Sets of Two-Dimensional Points} 	
 
\definition
An instance $S$ of the parameterized data type \name\ 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 S 
 
\create { }
   { creates an instance \var\ of type \name\ and initializes \var\ to
            the empty set. }
 
 
\operations 2.5 5
 
\op  point key {(ps\_item\ it)}
           {  returns the point of item $it$.\\
            \precond $it$ is an item in \var. }
 
 
\op  I inf {(ps\_item\ it)}
           {  returns the information of item $it$.\\
	    \precond $it$ is an item in \var. }
 
 
\op  ps\_item insert {(point\ p, \ I\ i)}
           {  associates the information $i$ with point $p$.
	   If there is an item $\<p,j\>$ in \var\ then $j$ 
	   is replaced by $i$, else a new item $\<p,i\>$ 
	   is added to $S$. In both cases the item is 
	   returned. }
 
 
\op  ps\_item lookup {(point\ p)}
           {  returns the item with point $p$ (nil if no
	   such item exists in \var). }
 
 
\op  ps\_item nearest\_neighbor {(point\ q)}
           {  returns the item $\<p,i\>\ \in\ S$ such that
	   the distance between $p$ and $q$ is minimal. }
 
 
\opl list\<ps\_item\> range\_search {(double\ x0, double\ x1, double\ y0, double\ y1)}
           {  returns all items $\<p,i\>\ \in\ S$ with\\
	   $x_0 \le p$.xcoord() $\le x_1$ and\\
	   $y_0 \le p$.ycoord() $\le y_1$. }
 
 
\op  list\<ps\_item\> convex\_hull {()}
           {  returns the list of items containing all points
	   of the convex hull of \var\ in clockwise order. }
 
 
\op  void del {(point\ p)}
           {  deletes the item with point $p$ from \var }
 
 
\op  void del\_item {(ps\_item\ it)}
           {  removes item $it$ from \var.\\
           \precond $it$ is an item in \var. }
 
 
\op  void change\_inf {(ps\_item\ it, \ I\ i)}
           {  makes $i$ the information of item $it$.\\
	   \precond $it$ is an item in \var. }
 
 
\op  list\<ps\_item\> all\_items {()}
           {  returns the list of all items in $S$. }
 
 
\op  list\<point\> all\_points {()}
           {  returns the list of all points in $S$. }
 
 
\op  void clear {()}
           {  makes \var\ the empty point\_set. }
 
 
\op  bool empty {()}
           {  returns true iff \var\ is empty. }
 
 
\op  int size {()}
           {  returns the size of \var. }
 
 
\implementation
Point sets are implemented by a combination of two-dimensional range trees
\cite{Wi85,Lu78} 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(n\log 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^2)$, if it follows any update operation (insert or
delete) and $O(\log n)$ otherwise. Here $n$ is the current size of the 
point set. The space requirement is $O(n^2)$.
 
