inria-00118781, version 4
Computing the exact arrangement of circles on a sphere, with applications in structural biology
Frederic Cazals
1Sebastien Loriot
1
N° RR-6049 (2007)
Résumé : Given a collection of circles on a sphere, we adapt the Bentley-Ottmann algorithm to the spherical setting to compute the {\em exact} arrangement of the circles. The algorithm consists of sweeping the sphere with a meridian, which is non trivial because of the degenerate cases and the algebraic specification of event points. From an algorithmic perspective, and with respect to general sweep-line algorithms, we investigate a strategy maintaining a linear size event queue. (The algebraic aspects involved in the development of the predicates involved in our algorithm are reported in a companion paper.) From an implementation perspective, we present the first effective arrangement calculation dealing with general circles on a sphere in an exact fashion, as exactness incurs a mere factor of two with respect to calculations performed using {\em double} floating point numbers on generic examples. In particular, we stress the importance of maintaining a linear size queue, in conjunction with arithmetic filter failures. From an application perspective, we present an application in structural biology. Given a collection of atomic balls, we adapt the sweep-line algorithm to report all balls covering a given face of the spherical arrangement on a given atom. This calculation is used to define molecular surface related quantities going beyond the classical exposed and buried solvent accessible surface areas. Spectacular differences w.r.t. traditional observations on protein - protein and protein - drug complexes are also reported.
- Domaine : Informatique/Géométrie algorithmique
- Mots-clés : Arrangement of circles – molecular surfaces – Van der Waals models
- Référence interne : RR-6049
- Commentaire : revision de la version de Decembre 2006
- Versions disponibles : v1 (06-12-2006) v2 (06-12-2006) v3 (06-12-2006) v4 (19-09-2007)
- inria-00118781, version 4
- http://hal.inria.fr/inria-00118781
- oai:hal.inria.fr:inria-00118781
- Contributeur : Frederic Cazals
- Soumis le : Mardi 18 Septembre 2007, 20:36:35
- Dernière modification le : Jeudi 2 Octobre 2008, 15:10:25






Documents associés
Exporter