home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12121 < prev    next >
Encoding:
Text File  |  1992-11-19  |  870 b   |  20 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: Polygon (or point) within an arbitrary polygon
  5. Message-ID: <1992Nov20.020732.2530@sophia.smith.edu>
  6. Organization: Smith College, Northampton, MA, US
  7. References: <HINKER.92Nov19081251@cocker.acl.lanl.gov> <1egv39INNj29@life.ai.mit.edu>
  8. Date: Fri, 20 Nov 1992 02:07:32 GMT
  9. Lines: 9
  10.  
  11. In article <1egv39INNj29@life.ai.mit.edu> sundar@ai.mit.edu writes:
  12. >This problem [polygon in polygon] ([...]) can be solved
  13. >by computing the convolution of the two polygons -- for which linear
  14. >time algorithms exist in the plane. 
  15.  
  16. The Minkowski sum of two polygons of n and m vertices can have
  17. Omega( n^2 m^2 ) vertices.  Thus if n=m, the size of the convolution
  18. can be proportional to n^4.
  19.     Perhaps you are making some assumptions about the two polygons?
  20.