🚀 go-pugleaf

          University of California at Santa Cruz
Baskin Center for Computer Engineering and Information Sciences 

The following technical report is available electronically or as
a paper copy.  Instructions for getting either follow the abstract.


UCSC-CRL-92-35   (available electronically as ucsc-crl-92-35.ps.Z)
DYNAMIC CONSTRAINED DELAUNEY TRIANGULATION AND APPLICATION TO MULTICHIP 
MODULE LAYOUT
Yizhi Lu  (M.S. Thesis)
December 1991, 46 pages (paper copy $8.00)

Abstract:  The *Voronoi diagram* is a partition of a set S of N points
in a plane, such that each region is the locus of the points (x, y)
closer to a point of S than to any other point of S.  If no four points
are co-circular, the *Delaunay triangulation* is the straight-line dual
of the Voronoi diagram.  The triangulation may be *constrained*, that
is, a set of straight-line segments may be prespecified.
     This thesis presents some characteristics of constrained Delaunay
triangulation and introduces a set of numerically stable algorithms for
incremently constructing and updating constrained Delaunay triangulation.
     The dynamic constrained Delaunay triangulation algorithms have been
implemented in a layout system for multichip modules.  It has been used
as the underlying data representation for rubber-band sketch, a
topological routing for one layer.
     We have proved the O(n log n) expected running time for the Delauney
triangulation algorithm.
Keywords:  Voronoi diagram, Delaunay triangulation, constrained Delauney
triangulation, layout, multichip module, topological routing.

This technical report is available electronically through either 
of the following methods:
1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
    as "anonymous", use your email address as your password, specify 
    "binary" before getting the file.  Uncompress before printing.
2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
    Put this command on the subject line or in the body of the message:
	@@ send ucsc-crl-92-35.ps.Z from tr
    To get the index or abstract list:
	@@ send INDEX from tr
	@@ send ABSTRACTS.1992 from tr
    To get the list of the tr directory:
	@@ list tr
    To get the list of commands and their syntax:
	@@ help commands

Order paper copies from:  Technical Library, Baskin Center for Computer 
Engineering & Information Sciences, UCSC, Santa Cruz  CA  95064.
Purchase orders are not accepted.  Checks or money orders must be
for U.S. dollars, payable through a U.S. bank, and made out to 
"UC Regents".

Questions:  jean@cse.ucsc.edu

===========================================================================
Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
	    compdoc-techreports-request@ftp.cse.ucsc.edu