home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / symbolic / 2054 < prev    next >
Encoding:
Text File  |  1992-07-23  |  1.1 KB  |  23 lines
  1. Newsgroups: sci.math.symbolic
  2. Path: sparky!uunet!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: Finding convex  hull ?
  5. Message-ID: <1992Jul23.115609.16096@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <1992Jul21.161451.8912@taloa.unice.fr> <1992Jul22.113118.24947@ai.univie.ac.at> <PHR.92Jul22170347@soda.berkeley.edu>
  8. Date: Thu, 23 Jul 1992 11:56:09 GMT
  9. Lines: 12
  10.  
  11. In article <PHR.92Jul22170347@soda.berkeley.edu> phr@soda.berkeley.edu (Paul Rubin) writes:
  12. >The best known algorithms for convex hull are very complicated.[...]
  13. >I believe "Compuational Geometry" by Preparata and Shamos has some
  14. >info on convex hull algorithms.
  15.  
  16.     Yes.  Graham's algorithm does not generalize to d > 2.  There
  17. are several algorithms that do generalize, however.  One is gift-wrapping.
  18. Another is beneath-beyond.  Both are described in P&S.  Edelsbrunner's
  19. book has a detailed description of beneath-beyond that is close to
  20. code.  The worstcase size of the hull of n points in d dimensions is
  21. n^{[d/2]} (that's floor of d/2), and the beneath-beyond algorithm
  22. nearly achieves that complexity.
  23.