Computing the exact arrangement of circles on a sphere, with applications in structural biology

Frédéric Cazals 1 Sebastien Loriot 1
1 GEOMETRICA - Geometric computing
INRIA Futurs, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : 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.
Type de document :
[Research Report] RR-6049, INRIA. 2007, pp.56
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger
Contributeur : Frederic Cazals <>
Soumis le : mardi 18 septembre 2007 - 20:36:35
Dernière modification le : samedi 27 janvier 2018 - 01:30:59
Document(s) archivé(s) le : lundi 22 octobre 2012 - 14:30:38


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00118781, version 4



Frédéric Cazals, Sebastien Loriot. Computing the exact arrangement of circles on a sphere, with applications in structural biology. [Research Report] RR-6049, INRIA. 2007, pp.56. 〈inria-00118781v4〉



Consultations de la notice


Téléchargements de fichiers