|
We developed a program (tess3) to compute power 3D Delaunay tessellation. Many existing programs can perform the same computation. Our goal is to improve the speed when the input are restricted to PDB files. Our experimental comparisons show that tess3 is robust and faster than the fastest program we have tested. These comparisons are detailed in the paper "A comparison of five implementations of 3d Delaunay tessellation" submitted to MSRI. We have also implemented functions for computing alpha shapes and visualization based on the fast Delaunay code. There are a few algorithmic and data structure results we haven't used for our current implementation of tess3, and more experimental results that will form the basis for another publication in summer 04.
(1) The numerical computations can be done based on ``sphere constructions"---a way to compute new spheres with old spheres rather than from point coordinates. This might further speed up the computation.
(2) We would like to handle the degeneracies in the input by computing Delaunay diagram directly. This avoids the perturbation of the input. It is also more natural with our ``sphere construction" approach.
(3) We have performed experiments comparing the effectiveness of using different space-filling curves for ordering the input points, which we would like to publish.
(4) We would like to implement functionalities to compute skin surfaces.