s'authentifier
version française rss feed

inria-00118781, version 4

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

Frederic Cazals () 1, Sebastien 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
  • oai:hal.inria.fr:inria-00118781
  • Contributeur : 
  • Soumis le : Mardi 18 Septembre 2007, 20:36:35
  • Dernière modification le : Jeudi 2 Octobre 2008, 15:10:25
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...
tous les articles de la base du CCSd...