Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!uwm.edu!cs.utexas.edu!sun-barr!ccut!titcca!etlcom!creamy!icspub!shinobu!chen
From: chen@shinobu.ics.osaka-u.junet (Chen Wei)
Newsgroups: comp.theory
Subject: Looking for an algorithm
Message-ID: <1375@icspub.ics.osaka-u.ac.jp>
Date: 19 Mar 90 08:18:59 GMT
Sender: news@icspub.ics.osaka-u.ac.jp
Reply-To: chen@ics.osaka-u.ac.jp
Lines: 18


 I am Wei Chen.I am a graduate student in Oosaka University,
Japan.
 I am working at the problems about finding intersections
of polygons recently. It was known the problem of testing
whether two n-vertex simple polygons intersect can be sloved
in time O(nlogn) and the lower bound of time for computing
this intersection is c*(nlogn+k)
(c is constant,k is the number of vertices of intersection).
But it seems there isn't any algorithm for computing inter-
section of two n-vertex simply polygons. if who knows it ,
please tell me. No matter how much time it uses and no matter
sequential algorithm or parallel algorithm.
 Thank you.

---
	Chen Wei
	chen@ics.osaka-u.ac.jp