[Sorry] Re: Re: [ REQ 5981]: Question about qhull

[daemon]

REQ 5981 is closed; must reopen it to assign someone.

... so the following mail message was not recorded:
From: Stuart Levy <slevy>
Date: Sat, 21 Sep 1996 18:55:24 -0500
Message-Id: <199609212355.SAA14050 at euclid.geom.umn.edu>
To: software@geom.umn.edu, software@geom.umn.edu
Subject: Re:  [ REQ 5981]: Question about qhull

>From barocas at cems.umn.edu Thu Aug 29 07:38:00 1996
Date: Thu, 29 Aug 1996 07:37:57 -0500 (CDT)
From: barocas at cems.umn.edu
To: software@geom.umn.edu
Subject: [ REQ 5981]: Question about qhull

> I am developing a model for foam mechanics, and I need to
> generate a 3D periodic Voronoi mesh.  I have downloaded
> qhull, and it generates a 3D mesh no problem, but I can't
> find an obvious way to get the periodicity.

Hi.  Sorry for the delay in replying, but I guess we don't immediately
think of something appropriate.  I think qhull could produce a voronoi
cell decomposition, but I think it's not very convenient, and you'd have
to create the periodic point set yourself.  However, a program by Daniel Huson
of the University of Bielefeld, may be relevant.  It's available from
    ftp://ftp.uni-bielefeld.de/pub/math/tiling/delone/delone.sgi.Z
That's a compressed UNIX tar package, including SGI binaries.   They don't
have it for other machines.  I don't know in what form it emits the
tiling, but possibly it'd be something you could use.

(Note that Delone == Delaunay, the guy for whom the dual of a Voronoi tiling
is named.)  In the same directory as delone.sgi.Z is a README file, namely:


Computing Periodic 3D Delone Tilings and Their Delaney Symbols      9.95
------------------------------------------------------------------------

Algorithms: Nikolai Dolbilin and Daniel Huson
Implementation: Daniel Huson
(dolbilin at class.main.su, huson at mathematik.uni-bielefeld.de)

I'm sending out this note to inform you on latest results obtained
by Nikolai Dolbilin and myself in the computation of periodic 3D Delone
tilings.

We are working on a program package DeloneTiles that takes as input
a periodic point set G*X, given by one of the 230 crystallographic groups
G and a finite list of points X. It produces as output the periodic
Delone tiling associated with the points. Obviously, it doesn't make sense
to assume that only four points can lie on a sphere (as is usually done in
the context of Delone diagrams), so the tiles computed are not necessarily
just simplices, but can be more complicated.

The idea of the approach is to reduce the computation to a finite subset
of points Y c G*X, then to apply a stable Delone triangulation program
such as Detri (author: Ernst Mucke, Department of Computer Science,
University of Illinois at Urbana-Champaign, mucke$@$cs.uiuc.edu) to Y
and then to take this triangulation and merge cospherical simplices
together to obtain bigger tiles, where appropriate.

We have worked out all necessary algorithms and have implemented them
in C++, using the LEDA library (Author Stefan Naeher, Max-Planck-Institut
fuer Informatik, Im Stadtwald, 6600 Saarbruecken, FRG, stefan$@$mpi-sb.mpg.de).
The code is written using CWEB (Authors: Silvio Levy and Donald E. Knuth).

The program package computes a translational domain in terms of a Delaney
symbol (as introduced by Andreas Dress). Moreover it contains a 
program that can be used to view the computed structure with the
help of the visualization program Geomview
(Authors: Stuart Levy, Tamara Munzner, Mark Phillips, Celeste Fowler,
Nathaniel Thurston, The Geometry Center,University of Minnesota,
1300 South Second Street, Minneapolis, MN  55454 USA,
software$@$geom.umn.edu).  It makes use of the discrete group feature of
Geomview which was written by Charlie Gunn.

Moreover, the programs compute the Delaney symbol w.r.t. the full symmetry
group and this can be used to compare computed tilings. Note that
a Delaney symbol is a triangulated orbifold, hence the programs
can be used to compute all 3D euclidean orbifolds.

We intend to apply the package to crystal-structures as found in
crystal-structure databases such as ICSD.

Another application is to use the programs to map out the different
Delone tilings associated with a given group (and choice of parameters for
the group). For example, we intend to choose points in a fundamental domain
for a given group at random, or on a grid, compute the corresponding periodic
Delone tiling and then compare the arising Delaney symbols. (Note that
two tilings are equivariantly equivalent if and only if the
corresponding Delaney symbols are isomorphic.)

The program package, compiled for SGI's, IRIX 5.2, is available from:
ftp.uni-bielefeld.de directory: pub/math/tiling/delone

Send questions and comments to: huson at mathematik.uni-bielefeld.de