home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / subdivis.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.8 KB  |  53 lines
  1. {\magonebf 6.6 Planar Subdivisions (subdivision)}
  2.  
  3. An instance $S$ of the data type $subdivision$ is a subdivision of the 
  4. two-dimensional plane, i.e., an embedded planar graph with straight
  5. line edges (see also sections 5.3 and 5.6). With each node $v$ of $S$ is 
  6. associated a point, called the position of $v$ and with each face of $S$ 
  7. is associated an information from a data type $I$, called the information 
  8. type of $S$.
  9.  
  10.  
  11. {\bf 1. Declaration}
  12.  
  13. \decl subdivision I 
  14.  
  15. introduces a new data type with name \name\ consisting of all 
  16. planar subdivisions with information type $I$. 
  17. \precond The data type $GRAPH(point,I)$ has been declared before.
  18.  
  19.  
  20.  
  21. {\bf 2. Creation of a subdivision}
  22.  
  23. \create S (GRAPH(point,I)\ G)
  24.  
  25. creates an instance \var\ of type \name\ and initializes it to 
  26. the subdivision represented by the parameterized directed graph $G$. 
  27. The node entries of $G$ (of type point)  define the positions of the 
  28. corresponding nodes of \var. Every face $f$ of \var\ is assigned the 
  29. information of one of its bounding edges in $G$.  \precond $G$ represents 
  30. a planar subdivision, i.e., a straight line embedded planar map.
  31.  
  32.  
  33. \bigskip
  34. {\bf 2. \operations}
  35. \medskip
  36. \+\op point  position {node\ v}       { returns the position of node $v$.}
  37. \smallskip
  38. \+\op ftype  inf      {face\ f}       { returns the information of face $f$.}
  39. \smallskip
  40. \+\op face   locate\_point {point\ p} { returns the face containing point $p$.}
  41. \smallskip
  42.  
  43.  
  44. \bigskip
  45. {\bf 3. Implementation}
  46.  
  47. Planar subdivisions are implemented by parameterized planar maps and an
  48. additional data structure for point location. Operations position and inf
  49. take constant time, a locate\_point operation takes time $O(\log^2 n)$.
  50. Here $n$ is the number of nodes.  The space requiremnt and the 
  51. initialization time is $O(n^2)$.
  52.  
  53.