D-V cells and fundamental domains for crystallographic groups, algorithms, and graphic realizations
This work is related to graphic software in progress by our department to the computer package CARAT, developed by colleagues in Aachen headed by Plesken. CARAT is available via http://wwwb.math.rwth-aachende/carat/. Our software intends to help the applicants, e.g., crystallographers, and others in modelling real crystals. Furthermore, it will hopefully be developed for visualization of higher-dimensional (d = 4) and non-Euclidean (d = 2, 3) investigations. The well-known algorithms for Dirichlet-Voronoi (D-V) cell partition of n points in general position (Voronoi diagram) in E-d have the worst case complexity [1] O (dn([d/2]+1)) + O (d(3)n([d/2]) log n). It becomes more simple for a fixed dimension d, if we assume a transitive group action on the point set. In particular, we consider a point orbit under a (crystallographic) space group Gamma in E-3, and determine its D-V cell D and-depending on the stabilizer of the starting point-a fundamental domain F for Gamma with an appropriate face pairing for a set of generators and algebraic presentation of Gamma. This latter algorithm with its graphic implementation is our new initiative in the topic. In general, the worst case time complexity exponentially increases only by the dimension d, but it is completely satisfactory for d = 2,3,4. (C) 2003 Elsevier Ltd. All rights reserved.
fundamental domains graphic implementation crystallographic groups in d-space algorithms for d-v cells