Path: utzoo!attcan!uunet!mailrus!tut.cis.ohio-state.edu!zaphod.mps.ohio-state.edu!rpi!wrf From: wrf@mab.ecse.rpi.edu (Wm Randolph Franklin) Newsgroups: comp.graphics Subject: Re: Triangulating Polygons Message-ID: Date: 7 Jun 90 15:19:51 GMT References: <5597@helios.TAMU.EDU> Organization: Rensselaer Polytechnic Institute, Troy NY Lines: 24 From uselton@wk39.nas.nasa.gov Thu Jun 7 03:20:18 1990 Date: Thu, 7 Jun 90 00:17:13 -0700 From: uselton@wk39.nas.nasa.gov (Samuel P. Uselton) To: wrf@ecse.rpi.edu I can't post from here, so please send this follow up to comp.graphics... I'm attending the Computational Geometry conference in Berkeley. On the program (and in the Proceedings) is Chazelle's n log*n algorithm for triangulating a polygon. It was announced today, verbally that he will present a linear time algorithm on Friday! Apparently the n log* n was finished around January, and the linear result is only a couple of weeks old. Maria Klawe has already seen it, believes it, and believes that a simpler refinement is a matter of time. Good news, eh? Sam Uselton employed by CSC working for NASA speaking for myself uselton@nas.nasa.gov -- Wm. Randolph Franklin Internet: wrf@ecse.rpi.edu (or @cs.rpi.edu) Bitnet: Wrfrankl@Rpitsmts Telephone: (518) 276-6077; Telex: 6716050 RPI TROU; Fax: (518) 276-6261 Paper: ECSE Dept., 6026 JEC, Rensselaer Polytechnic Inst, Troy NY, 12180