home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / infosyst / gis / 4549 < prev    next >
Encoding:
Text File  |  1992-12-22  |  2.3 KB  |  57 lines
  1. Comments: Gated by NETNEWS@AUVM.AMERICAN.EDU
  2. Path: sparky!uunet!cs.utexas.edu!sdd.hp.com!swrinde!gatech!darwin.sura.net!paladin.american.edu!auvm!MATGEN.GE.CNR.IT!FRANKLIN
  3. X-Envelope-to: gis-l@UBVM.cc.buffalo.edu
  4. X-VMS-To: ICE622::IN%"gis-l@UBVM.cc.buffalo.edu"
  5. X-VMS-Cc: FRANKLIN
  6. Message-ID: <B0C007DDC0A00249@ICE.GE.CNR.IT>
  7. Newsgroups: comp.infosystems.gis
  8. Date:         Tue, 22 Dec 1992 18:38:00 MET
  9. Sender:       Geographic Information Systems Discussion List <GIS-L@UBVM.BITNET>
  10. From:         Wm Randolph Franklin <FRANKLIN@MATGEN.GE.CNR.IT>
  11. Subject:      Complexity of updating a Voronoi diagram
  12. Lines: 43
  13.  
  14. On Dec 11, srobeson@bronze.ucs.indiana.edu (scott robeson),
  15. in an article on Re: Voronoi Tessalation GIS, said this:
  16.  
  17.    In some ill-conditioned distributions of control points,
  18.    however, the Voronoi tesselation can change dramatically
  19.    just by adding or removing a few points in strategic
  20.    locations.
  21.  
  22. The question is, how often does that occur in practice?
  23.  
  24. If you're given all the points in advance, and process them
  25. in random order, then the expected total time is excellent,
  26. i.e., N*log(N) or N*log(N)^2 (I forget which).   The
  27. expectation is over the random number generator in the
  28. program; every time you run the program it will take a
  29. slightly different time to produce the same output.  There
  30. is no input data whose expected time is worse.
  31.  
  32. This is an example of a Las Vegas randomized algorithm in
  33. computational geometry.  It is a dramatic concept only about
  34. 5 years old, which leads to algorithms both faster and
  35. simpler.  (The tradeoff is that they can be very hard to
  36. analyze.)
  37.  
  38. If the user is specfying the points, and they must be
  39. processed "on-line" 1-by-1 as given, then the time can blow
  40. up to quadratic.
  41.  
  42. I don't think that such a circumstance is worth worryinbg
  43. about since I'd doubt it would occur in a real example.
  44. However, even then, I could imagine a multi-level Voronoi
  45. diagram that might handle that.   The idea would be to
  46. insert troublesome new points into a temporary, smaller data
  47. structure.  From time to time merge the data structures.
  48. All queries must be done in the two data structures.
  49.  
  50. Now let the "two" be a variable depending on the number of
  51. points.
  52.  
  53. The idea was described by Jon Bentley and Mary Shaw (I
  54. think) as a general technique for dynamizing static data
  55. structures in IEEE Trans. on Software Engin. at least 15
  56. years ago.
  57.