home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / point_se.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  4.4 KB  |  119 lines
  1. {\magonebf  6.3 Sets of two-dimensional points (point\_set)}
  2.  
  3. An instance $S$ of the data type $point\_set$ is a collection of items 
  4. ($ps\_item$). Every item in $S$ contains a two-dimensional point as key
  5. (data type $point$), and an information from a data type $I$, called 
  6. the information type of $S$. The number of items in $S$ is called the size of 
  7. $S$. A point set of size zero is said to be empty. We use $<p,i>$ to denote the 
  8. item with point $p$, and information $i$. For each  point $p$ there is at most 
  9. one item $<p,i> \in S$. Beside the normal dictionary operations, the data
  10. type $point\_set$ provides operations for rectangular range queries and
  11. nearest neighbor queries. 
  12.  
  13.  
  14. \bigskip
  15. {\bf 1. Declaration of a two-dimensional point set type}
  16.  
  17. \decl point\_set I
  18.  
  19. introduces a new data type with name \name\ consisting of all 
  20. two-dimensional point sets  with information type $I$. 
  21.  
  22.  
  23. \bigskip
  24. {\bf 2. Creation of a two-dimensional point set}
  25.  
  26.  
  27. \create S {}
  28.  
  29. creates an instance \var\ of type \name\ and initializes \var\ to the 
  30. empty set. 
  31.  
  32.  
  33.  
  34. \bigskip
  35. {\bf 3. \operations}
  36.  
  37. \+\cleartabs & \hskip 2.6truecm & \hskip 6truecm &\cr
  38. \+\op point          key {ps\_item\ it}   
  39.                       {returns the point of item $it$.}
  40. \+\nop                {\precond $it$ is an item in \var.}
  41. \smallskip
  42. \+\op I              inf {ps\_item\ it}   
  43.                       {returns the information of item $it$.}
  44. \+\nop                {\precond $it$ is an item in \var.}
  45. \smallskip
  46. \+\op ps\_item       insert {point\ p,\ I\ i} 
  47.                       {associates the information $i$ with point $p$.}
  48. \+\nop                {If there is an item $<p,j>$ in \var\ then $j$}
  49. \+\nop                {is replaced by $i$, else a new item $<p,i>$}
  50. \+\nop                {is added to $S$. In both cases the item is}
  51. \+\nop                {returned.}
  52. \smallskip
  53. \+\op ps\_item       lookup {point\ p} 
  54.                       {returns the item with point $p$ (nil if no}
  55. \+\nop                {such item exists in \var).}
  56. \smallskip
  57. \+\op ps\_item       nearest\_neighbor {point\ q}
  58.                       {returns the item $<p,i>\ \in\ S$ such that}
  59. \+\nop                {the distance between $p$ and $q$ is minimal.}
  60. \smallskip
  61. \+\op list(ps\_item) range\_search {real\ x_0,\ real\ x_1,\ real\ y_0,\ real\ y_1}  {}
  62. \+\nop                {returns all items $<p,i>\ \in\ S$ with}
  63. \+\nop                {$x_0 \le p$.xcoord() $\le x_1$ and}
  64. \+\nop                {$y_0 \le p$.ycoord() $\le y_1$}
  65. \smallskip
  66. \+\op list(ps\_item) convex\_hull {}
  67.                       {returns the list of items containing all}
  68. \+\nop                {points of the convex hull of \var\ in clock-}
  69. \+\nop                {wise order.}
  70. \smallskip
  71. \+\op void           del {point\ p}         
  72.                       {deletes the item with point $p$ from \var}
  73. \smallskip
  74. \+\op void           del\_item {ps\_item it}   
  75.                               {removes item $it$ from \var.}
  76. \+\nop                        {\precond $it$ is an item in \var.}
  77. \smallskip
  78. \+\op void           change\_inf {ps\_item\ it,\ I\ i} 
  79.                               {makes $i$ the information of item $it$.}
  80. \+\nop                        {\precond $it$ is an item in \var.}
  81. \smallskip
  82. \+\op list(ps\_item) all\_items {}
  83.                               {returns the list of all items in $S$. }
  84. \smallskip
  85. \+\op list(point)    all\_points {}
  86.                               {returns the list of all points in $S$. }
  87. \smallskip
  88. \+\op void           clear {} 
  89.                               {makes \var\ the empty point\_set.}
  90. \smallskip 
  91. \+\op bool           empty {} 
  92.                               {returns true iff \var\ is empty.}
  93. \smallskip 
  94. \+\op int            size {}  
  95.                               {returns the size of \var.}
  96.  
  97.  
  98.  
  99. \bigskip
  100. {\bf 4. Iteration}
  101.  
  102. {\bf forall\_ps\_items}($i,S$) 
  103. $\{$ ``the items of $S$ are successively assigned to $i$ '' $\}$
  104.  
  105.  
  106.  
  107. \bigskip
  108. {\bf 5. Implementation}
  109.  
  110. Point sets are implemented by a combination of two-dimensional range trees
  111. and Voronoi diagrams.  Operations insert, lookup, del\_item, del 
  112. take time $O(\log^2 n)$, key, inf, empty, size, change\_inf take time $O(1)$, 
  113. and clear takes time $O(n\log n)$. A range\_search operation takes time
  114. $O(k+\log^2 n)$, where $k$ is the size of the returned list. A nearest\_neighbor
  115. query takes time $O(n^2)$, if it follows any update operation (insert or
  116. delete) and $O(log n)$ otherwise. Here $n$ is the current size of the 
  117. point set. The space requirement is $O(n^2)$.
  118.  
  119.