\manpage {subdivision} {I} {Planar Subdivisions}
 
\definition
An instance $S$ of the parameterized data type \name\ is a
subdivision of the two-dimensional plane, i.e., an embedded planar graph
with straight line edges (see also sections \ref{Planar Maps} and
\ref{Parameterized Planar Maps}). With each node
$v$ of $S$ is associated a point, called the position of $v$ and with each
face of $S$ is associated an information from data type $I$, called the
information type of $S$.
 
\creation S 
 
\create {(GRAPH\<point,I\>\ G)}
   {
creates an instance \var\ of type \name\ and initializes it to
the subdivision represented by the parameterized directed graph $G$.
The node entries of $G$ (of type point)  define the positions of the
corresponding nodes of \var. Every face $f$ of \var\ is assigned the
information of one of its bounding edges in $G$.\\
\precond $G$ represents
a planar subdivision, i.e., a straight line embedded planar map. }
 
 
\operations 2 4.5
 
\op  point position {(node\ v)}
           {  returns the position of node $v$. }
 
 
\op  I inf {(face\ f)}
           {  returns the information of face $f$. }
 
 
\op  face locate\_point {(point\ p)}
           {  returns the face containing point $p$. }
 
 
\implementation
Planar subdivisions are implemented by parameterized planar maps and an
additional data structure for point location based on persistent search trees
\cite{DSST89}. Operations position and inf take constant time, a locate\_point 
operation takes time $O(\log^2 n)$. Here $n$ is the number of nodes. 
The space requirement and the initialization time is $O(n^2)$.
 
