s.geom(1)		      Grass User's Manual		     s.geom(1)



NNAAMMEE
       ss..ggeeoomm	- Computes Delaunay triangulation, MinMax-Angle triangulation,
       MinMax-Slope triangulation, MaxMin-Height triangulation, Regular trian-
       gulation, planesweep triangulation, Voronoi diagram, and convex hull of
       sites in 2 and 2 1/2 dimensions.

SSYYNNOOPPSSIISS
       ss..ggeeoomm
       ss..ggeeoomm hheellpp
       ss..ggeeoomm iinnppuutt==_n_a_m_e oouuttppuutt==_n_a_m_e [pprreecciissiioonn==_v_a_l_u_e] [ooppeerraattiioonn==_n_a_m_e]

DDEESSCCRRIIPPTTIIOONN
       _s_._g_e_o_m takes a sites file as input and computes various triangulations,
       the  Voronoi diagram, or the convex hull of the sites. The z-coordinate
       is read from the description field if it is specified, otherwise  0  is
       assumed.  The  z-coordinate  is used for the MinMax-slope triangulation
       and for the regular triangulation  (where  it  is  interpreted  as  the
       weight  of  the	site).	For all other computations the z-coordinate is
       ignored.


       The MinMax-angle triangulation is the triangulation for the sites which
       minmizes  (lexicographically)  the  sorted  vector of all the angles of
       triangles in the triangulation. The MaxMin-height and MinMax-slope tri-
       angulations  are similar.  The algorithms used for the computations are
       not heuristics, they actually achieve the optimum.


       The regular triangulation is the weighted version of the delaunay  tri-
       angulation  (weights are assigned to the sites, the delaunay triangula-
       tion corresponds to the regular triangulation where all the sites  have
       identical weights).


       The output is saved in vector file format.

OOPPTTIIOONNSS
   PPaarraammeetteerrss::
       iinnppuutt==_n_a_m_e
	      Input vector (level 2) file.

       oouuttppuutt==_n_a_m_e
	      Output vector file.

       pprreecciissiioonn==_v_a_l_u_e
	      Number   of  significant	positions  after  the  decimal	point.
	      (default is 0).

       ooppeerraattiioonn==_n_a_m_e
	      One of the following: _s_w_e_e_p,  _d_e_l_a_u_n_a_y,  _a_n_g_l_e,  _h_e_i_g_h_t,	_s_l_o_p_e,
	      _h_u_l_l. These correspond to the planesweep triangulation, Delaunay
	      triangulation, MinMax-angle triangulation, MaxMin-height	trian-
	      gulation,  MinMax-slope  triangulation,  regular	triangulation,
	      Voronoi diagram, and convex  hull,  respectively.   (default  is
	      Delaunay triangulation).


NNOOTTEE
       Only the sites which fall into the current region are used for the com-
       putations.


       The computation times for the various operations  depends  strongly  on
       the algorithm used.


       The plansweep triangulation and convex hull computation require _O_(_n _l_o_g
       _n_) operations in the worst case [Ed].   The  Delaunay  heuristic  needs
       _O_(_n_^_2_) time in the worst case, however it performs much faster in prac-
       tice. The MinMax-angle and MaxMin-height triangulations need _O_(_n_^_2  _l_o_g
       _n_)  operations  [EdTa], and the MinMax-slope triangulation needs _O_(_n_^_3_)
       operations [BeEd].


       Internally, the coordinates of the sites are stored in  fix-point  for-
       mat.   Therefore, the number of decimal digits cannot exceed 64 bit (or
       apprx.  16 decimal digits).

BBUUGGSS
       Some fields of the header in the output file are not properly set.

RREEFFEERREENNCCEESS
       [BeEd] M.Bern, H. Edelsbrunner, D.  Eppstein,  S.  Mitchel,  T.S.  Tan.
       Edge Insertion for Optimal Triangulations.  _I_n _P_r_o_c_. _1_s_t _L_a_t_i_n _A_m_e_r_i_c_a_n
       _S_y_m_p_o_s_. _T_h_e_o_r_e_t_.  _I_n_f_o_r_m_a_t_i_c_s _1_9_9_2, 46--60.


       [Ed] H. Edelsbrunner.  _A_l_g_o_r_i_t_h_m_s _i_n _C_o_m_b_i_n_a_t_o_r_i_a_l _G_e_o_m_e_t_r_y_.  Springer-
       Verlag, Heidelberg, Germany, 1987.


       [EdSh]  H.  Edelsbrunner,  N.  R. Shah.	Incremental Flipping Works for
       Regular Triangulations.	_I_n _P_r_o_c_. _8_t_h _A_n_n_. _S_y_m_p_o_s_. _C_o_m_p_u_t_. _G_e_o_m_.  _1_9_9_2,
       43-52.


       [EdTa]  H.  Edelsbrunner, T.S. Tan and R. Waupotitsch.  An O(n^2 log n)
       Time Algorithm for  the	MinMax	Angle  Triangulation.	_S_I_A_M  _J_.  _S_c_i_.
       _S_t_a_t_i_s_t_. _C_o_m_p_u_t_. _1_3 _1_9_9_2, 994-1008.

SSEEEE AALLSSOO
       _v_._g_e_o_m

AAUUTTHHOORR
       Roman Waupotitsch

       _L_a_s_t _c_h_a_n_g_e_d_: _$_D_a_t_e_: _2_0_0_2_/_0_1_/_2_5 _0_5_:_4_5_:_3_5 _$



GRASS 5.0							     s.geom(1)
