home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #30 / NN_1992_30.iso / spool / comp / graphics / 12847 < prev    next >
Encoding:
Text File  |  1992-12-13  |  1.4 KB  |  37 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!news.smith.edu!orourke
  3. From: orourke@sophia.smith.edu (Joseph O'Rourke)
  4. Subject: Re: How to find minimal bounding circle of a polygon?
  5. Message-ID: <1992Dec14.021651.14044@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <24405@hacgate.SCG.HAC.COM>
  8. Date: Mon, 14 Dec 1992 02:16:51 GMT
  9. Lines: 26
  10.  
  11. In article <24405@hacgate.SCG.HAC.COM> shek@aic.hrl.hac.com (Eddie C. Shek) writes:
  12. >[...] the minimal bounding circle is defined as
  13. >the smallest circle that covers the polygon.
  14. >
  15. >Are there any algorithms that find the minimal bounding circle
  16. >of a 2-D polygon (or equivalently, a set of 2-D points)?
  17.  
  18. Yes.  There is a beautiful connection between this problem and the
  19. furthest-point Voronoi diagram:  the center of a minimum spanning
  20. circle lies on this diagram, at a vertex if the circle touches
  21. the polygon at three points.  So constructing the f-p Vor diag.
  22. almost gets you there.  And that diagram is easily obtained from
  23. a three-dimensional convex hull.
  24.     But this is not the only way to do it.  An unusual approach
  25. can be found in this paper:
  26.  
  27. @incollection{Melville
  28. , author =    "R. C. Melville"
  29. , title =    "An implementation study of two algorithms for the minimum spanning circle problem"
  30. , editor =    "G. T. Toussaint"
  31. , booktitle =    "Computational Geometry"
  32. , publisher =    "North-Holland"
  33. , address =    "Amsterdam, Netherlands"
  34. , year =    1985
  35. , pages =    "267--294"
  36. }
  37.