home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / doc / techrepo / 232 < prev    next >
Encoding:
Internet Message Format  |  1993-01-05  |  3.3 KB
  1. Path: sparky!uunet!cs.utexas.edu!sun-barr!olivea!hal.com!darkstar.UCSC.EDU!golding
  2. From: jean@cse.ucsc.edu (Jean McKnight)
  3. Newsgroups: comp.doc.techreports
  4. Subject: UCSC TR: Dyamic Constrained Delauney Triangulation and Application to Multichip Module Layout
  5. Keywords: Voronoi diagram, Delaunay triangulation, constrained Delauney
  6. Message-ID: <1ic5ltINNkep@darkstar.UCSC.EDU>
  7. Date: 5 Jan 93 14:23:57 GMT
  8. Organization: University of California, Santa Cruz (CE/CIS Boards)
  9. Lines: 59
  10. Approved: compdoc-techreports@ftp.cse.ucsc.edu
  11. NNTP-Posting-Host: oak.ucsc.edu
  12. Originator: golding@oak
  13.  
  14.  
  15.           University of California at Santa Cruz
  16. Baskin Center for Computer Engineering and Information Sciences 
  17.  
  18. The following technical report is available electronically or as
  19. a paper copy.  Instructions for getting either follow the abstract.
  20.  
  21.  
  22. UCSC-CRL-92-35   (available electronically as ucsc-crl-92-35.ps.Z)
  23. DYNAMIC CONSTRAINED DELAUNEY TRIANGULATION AND APPLICATION TO MULTICHIP 
  24. MODULE LAYOUT
  25. Yizhi Lu  (M.S. Thesis)
  26. December 1991, 46 pages (paper copy $8.00)
  27.  
  28. Abstract:  The *Voronoi diagram* is a partition of a set S of N points
  29. in a plane, such that each region is the locus of the points (x, y)
  30. closer to a point of S than to any other point of S.  If no four points
  31. are co-circular, the *Delaunay triangulation* is the straight-line dual
  32. of the Voronoi diagram.  The triangulation may be *constrained*, that
  33. is, a set of straight-line segments may be prespecified.
  34.      This thesis presents some characteristics of constrained Delaunay
  35. triangulation and introduces a set of numerically stable algorithms for
  36. incremently constructing and updating constrained Delaunay triangulation.
  37.      The dynamic constrained Delaunay triangulation algorithms have been
  38. implemented in a layout system for multichip modules.  It has been used
  39. as the underlying data representation for rubber-band sketch, a
  40. topological routing for one layer.
  41.      We have proved the O(n log n) expected running time for the Delauney
  42. triangulation algorithm.
  43. Keywords:  Voronoi diagram, Delaunay triangulation, constrained Delauney
  44. triangulation, layout, multichip module, topological routing.
  45.  
  46. This technical report is available electronically through either 
  47. of the following methods:
  48. 1.  through anonymous ftp from ftp.cse.ucsc.edu, in /pub/tr. Log in 
  49.     as "anonymous", use your email address as your password, specify 
  50.     "binary" before getting the file.  Uncompress before printing.
  51. 2.  by mail to automatic mail server rnalib@ftp.cse.ucsc.edu.
  52.     Put this command on the subject line or in the body of the message:
  53.     @@ send ucsc-crl-92-35.ps.Z from tr
  54.     To get the index or abstract list:
  55.     @@ send INDEX from tr
  56.     @@ send ABSTRACTS.1992 from tr
  57.     To get the list of the tr directory:
  58.     @@ list tr
  59.     To get the list of commands and their syntax:
  60.     @@ help commands
  61.  
  62. Order paper copies from:  Technical Library, Baskin Center for Computer 
  63. Engineering & Information Sciences, UCSC, Santa Cruz  CA  95064.
  64. Purchase orders are not accepted.  Checks or money orders must be
  65. for U.S. dollars, payable through a U.S. bank, and made out to 
  66. "UC Regents".
  67.  
  68. Questions:  jean@cse.ucsc.edu
  69.  
  70. ===========================================================================
  71. Co-moderator:  Richard Golding, Computer & Information Sciences, UC Santa Cruz
  72.         compdoc-techreports-request@ftp.cse.ucsc.edu
  73.