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. ll-known algorithms for Dirichlet-Voronoi (D-V) cell partition of n points in general position (Voronoi diagram) in Ed have the worst case complexity [1] O(dn⌈d2⌉+1)+O(d3n⌈d2⌉logn). omes more simple for a fixed dimension d, if we assume a transitive group action on the point set. ticular, we consider a point orbit under a (crystallographic) space group Γ in E3, and determine its D-V cell D and—depending on the stabilizer of the starting point—a fundamental domain F for Γ with an appropriate face pairing for a set of generators and algebraic presentation of Γ 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.