| In conjunction with the effort reported on the previous
page, we have been exploring the incremental recomputation of the inclusion/exclusion
formulas used for the calculation of area, volume, and their derivatives.
The formulas are currently obtained by explicitly recomputing the alpha
complex after each simulation step. Even though that computation has been
sped up significantly, further speed ups may be possible by an incremental
approach. Unfortunately, the Delaunay complex on which the alpha complex
is based, is a fragile structure under motion and can undergo numerous combinatorial
changes even under slight motions of the atoms in the molecule. To avoid
the bottleneck, we have been exploring combinatorial structures sufficient
for deriving equivalent inclusion-exclusion formulas, but which are more
stable under motion. Such structures exist as subcomplexes of almost-Delaunay
triangulations. We show that the inclusion-exclusion formula is correct
provided the simplices that correspond to the terms are combinatorialy independent.
Initial computational experiments indicate that the frequency of violating
the independence of a simplex is less than 10% of the frequency of violating
its Delauynayhood. The goal of this project is to maintain such almost-Delaunay
triangulations or their relevant subcomplexes under motion that is typical
for molecular dynamics computations. For new overlaps between spheres, we
use the sphere detection hierarchies mentioned above. The remaining problem
is the maintenance of almost-Delaunayhood, and we look into extensions of
the classic flip algorithms for Delaunay triangulations.
|
