We describe a software package for computing and manipulating the
subdivision of a sphere by a collection of (not necessarily great)
circles and for computing the boundary surface of the union of
spheres. We present problems that arise in the implementation of the
software and the solutions that we have found for them. At the core of
the paper is a novel perturbation scheme to overcome degeneracies and
precision problems in computing spherical arrangements while using
floating point arithmetic. The scheme is relatively simple, it
balances between the efficiency of computation and the magnitude of
the perturbation, and it performs well in practice. We report and
discuss experimental results. Our package is a major component in a
larger package aimed to support geometric queries on molecular models;
it is currently employed by chemists working in `rational drug
design'. The spherical subdivisions are used to construct a geometric
model of a molecule where each sphere represents an atom. We also
give an overview of the molecular modeling package and detail
additional features and implementation issues.
Links
Dan Halperin and
Christian R. Shelton
A perturbation scheme for spherical arrangements with application to
molecular modeling
Comput. Geom. Theory Appl., vol. 10, 1998, pp 273--287.
Proc. 13th Annu. ACM Sympos. Comput. Geom., 1997, pp 183--192.
![[Molecule]](../images/molecule.gif)
![[Projects Page]](../images/icons/projects.gif){kind=icon}
![[Top]](../images/icons/top.gif){kind=icon}
