home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #27 / NN_1992_27.iso / spool / comp / graphics / 12226 < prev    next >
Encoding:
Internet Message Format  |  1992-11-22  |  2.0 KB
  1. Path: sparky!uunet!olivea!charnel!sifon!thunder.mcrcim.mcgill.edu!snorkelwacker.mit.edu!ai-lab!fiber-one!sundar
  2. From: sundar@fiber-one.ai.mit.edu (Sundar Narasimhan)
  3. Newsgroups: comp.graphics
  4. Subject: Re: Polygon (or point) within an arbitrary polygon
  5. Message-ID: <1ep7ulINNqu2@life.ai.mit.edu>
  6. Date: 23 Nov 92 00:17:25 GMT
  7. References: <HINKER.92Nov19081251@cocker.acl.lanl.gov> <1egv39INNj29@life.ai.mit.edu> <1992Nov20.020732.2530@sophia.smith.edu>
  8. Sender: sundar@fiber-one (Sundar Narasimhan)
  9. Reply-To: sundar@ai.mit.edu
  10. Organization: MIT Artificial Intelligence Laboratory
  11. Lines: 24
  12. NNTP-Posting-Host: fiber-one.ai.mit.edu
  13.  
  14. In article <1992Nov20.020732.2530@sophia.smith.edu>, orourke@sophia.smith.edu (Joseph O'Rourke) writes:
  15. |> In article <1egv39INNj29@life.ai.mit.edu> sundar@ai.mit.edu writes:
  16. |> >This problem [polygon in polygon] ([...]) can be solved
  17. |> >by computing the convolution of the two polygons -- for which linear
  18. |> >time algorithms exist in the plane. 
  19. |> 
  20. |> The Minkowski sum of two polygons of n and m vertices can have
  21. |> Omega( n^2 m^2 ) vertices.  Thus if n=m, the size of the convolution
  22. |> can be proportional to n^4.
  23. |>     Perhaps you are making some assumptions about the two polygons?
  24. Yes, I was. For convex polygons A and B there is an O(n+m) algorithm 
  25. (see Guibas et al. "Kinetic Framework for Computational Geometry"
  26. 24'th FOCS 83).
  27.  
  28. Now, for the more interesting case when A, B can be concave. Is there
  29. a bound on the number of bounding outer edges/vertices of the Minkowski sum
  30. (since this is all one would need to compute)? For special cases, i.e. when
  31. the number of concavities in A + B is odd (say k), the above algorithm can be 
  32. modified to work in O(n+m) time. A friend and I tried our hand at the
  33. general case but couldn't get any better than O(n*m) -- and ended up
  34. concluding that our attempts at mapping R^2xSO(1) to R^2xSO(k) had the
  35. right sort of flavor, but was missing something fundamental that some
  36. mathematician familiar with this could probably whiz thru in a second. 
  37. Any further thoughts?
  38.