Dartmouth logo Dartmouth College Computer Science
Technical Report series
CS home
TR home
TR search TR listserv
By author: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
By number: 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986

Multiplicatively Weighted Crystal Growth Voronoi Diagrams (Thesis)
Barry F. Schaudt
Dartmouth PCS-TR92-177


Voronoi diagrams and variants of Voronoi diagrams have been used for many years to model crystal growth. If the boundary of the growing crystals are circular and all the crystals start at the same time and have the same constant growth rate, then the Voronoi diagram is used to model the growth. If the crystals start at different times, the additively weighted Voronoi diagram is used to model the crystal growth. In this thesis, I propose a new type of Voronoi diagram called the multiplicatively weighted crystal growth Voronoi diagram, that can be used to model crystal growth when the crystals have different constant growth rates. In this new model, the distance from a site to a point in its region is measured along a shortest path lying entirely within the region. In the multiplicatively weighted crystal growth Voronoi diagram, a growing crystal (or region) may "wrap around" another site's region. When a region wraps around, distances from the site are in part measured along the boundary of the two regions, treating one of the regions as an obstacle, rather than along a straight line that passes through the region.

The worst case size of the multiplicatively weighted crystal growth Voronoi, diagram is 0(n 2). To construct the diagram, techniques from numerical analysis are used to approximate and to intersect curves described by a system of first order differential equations. Numerical methods to approximated a curve construct a polygonal approximation of the curve. One step of the numerical methods constructs an edge of the polygonal approximation. In the new Voronoi diagram, a step may require 0(n ) constant time operations. Let S be the number of steps required by the numerical method used just to draw the diagram. In the worst case, the algorithm presented in this thesis requires O (n 3) intersection calculations plus O (nS lg S ) time using O (n 3 + S ) space. A variant of this algorithm requires O (n 3) intersection calculations plus O (nS 2 + n 2S ) time using O (n 2) space.

Also presented are some variants of the new Voronoi diagram. One of these variants uses a convex polygon distance function. The multiplicatively weighted crystal growth Voronoi diagram using a convex polygon distance function does not require numerical methods to construct.

PDF PDF (4064KB)

Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]

Or copy and paste:
   Barry F. Schaudt, "Multiplicatively Weighted Crystal Growth Voronoi Diagrams (Thesis)." Dartmouth Computer Science Technical Report PCS-TR92-177, 1992.

Notify me about new tech reports.

Search the technical reports.

To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu

Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Technical reports collection maintained by David Kotz.