Xref: utzoo comp.sys.sgi:8114 comp.graphics:15804
Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!sdd.hp.com!think.com!linus!agate!miro.Berkeley.EDU!seth
From: seth@miro.Berkeley.EDU (Seth Teller)
Newsgroups: comp.sys.sgi,comp.graphics
Subject: constrained (Delaunay) triangulation
Keywords: triangulation, constrained
Message-ID: <1991Feb6.073039.25229@agate.berkeley.edu>
Date: 6 Feb 91 07:30:39 GMT
Sender: usenet@agate.berkeley.edu (USENET Administrator)
Reply-To: seth@miro.Berkeley.EDU (Seth Teller)
Organization: University of California at Berkeley
Lines: 16

has anyone implemented constrained triangulation in 2-D?  i have
a point set and some collection of non-intersecting edges over 
the set.  i want a triangulation over the set that includes the
edges i specify beforehand.  furthermore, i want to compute this
thing in O(n lg n) time and space.

there is an extension of steve fortune's algorithm that does
this, but as far as i know it has not been implemented.  does
anyone have or know of code to do this?  i'd rather not waste
a week hacking on a done problem.

thanks,

seth

ps: comp.graphics people please email, don't post-- thanks again.