home *** CD-ROM | disk | FTP | other *** search
- Newsgroups: comp.graphics
- Path: sparky!uunet!news.smith.edu!orourke
- From: orourke@sophia.smith.edu (Joseph O'Rourke)
- Subject: Re: Polygon (or point) within an arbitrary polygon
- Message-ID: <1992Nov20.020732.2530@sophia.smith.edu>
- Organization: Smith College, Northampton, MA, US
- References: <HINKER.92Nov19081251@cocker.acl.lanl.gov> <1egv39INNj29@life.ai.mit.edu>
- Date: Fri, 20 Nov 1992 02:07:32 GMT
- Lines: 9
-
- In article <1egv39INNj29@life.ai.mit.edu> sundar@ai.mit.edu writes:
- >This problem [polygon in polygon] ([...]) can be solved
- >by computing the convolution of the two polygons -- for which linear
- >time algorithms exist in the plane.
-
- The Minkowski sum of two polygons of n and m vertices can have
- Omega( n^2 m^2 ) vertices. Thus if n=m, the size of the convolution
- can be proportional to n^4.
- Perhaps you are making some assumptions about the two polygons?
-