Personal tools
You are here: Home Projects In-house Projects Controlled Perturbation of Spheres
« October 2017 »
October
SuMoTuWeThFrSa
1234567
891011121314
15161718192021
22232425262728
293031
Log in


Forgot your password?
 

Controlled Perturbation of Spherical Arrangements

[Molecule]

Abstract

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
    • Computational Geometry: Theory and Applications, 10: 273-28, 1998 [link] [bibtex]
    • In Proceedings of the 13th Annual ACM Symposium of Computational Geometry, pages 183-192, 1997 [link] [bibtex]
    • MIT AI MEMO 1618, 1997

Contact

Dan Halperin http://acg.cs.tau.ac.il/danhalperin halperin@post.tau.ac.il
Document Actions