Computing the Arrangement of Circles on a Sphere, with Applications in Structural Biology

Frédéric Cazals 1, * Sebastien Loriot 1, 2
* Auteur correspondant
1 ABS - Algorithms, Biology, Structure
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Balls and spheres are the simplest modeling primitives after affine ones, which accounts for their ubiquitousness in Computer Science and Applied Mathematics. Amongst the many applications, we may cite their prevalence when it comes to modeling our ambient 3D space, or to handle molecular shapes using Van der Waals models. If most of the applications developed so far are based upon simple geometric tests between balls, in particular the intersection test, a number of applications would obviously benefit from finer pieces of information. Consider a sphere $S_0$ and a list of circles on it, each such circle stemming from the intersection between $S_0$ and another sphere, say $S_i$. Also assume that $S_i$ has an accompanying ball $B_i$. This paper develops an integrated framework, based on the generalization of the Bentley-Ottmann algorithm to the spherical setting, to (i)compute the exact arrangement of circles on $S_0$ (ii)construct in a single pass the half-edge data structure encoding the arrangement induced by the circles (iii)report the covering list of each face of this arrangement, i.e. the list of balls containing it. As an illustration, the covering lists are used as the building block of a geometric optimization algorithm aiming at selecting diverse conformational ensembles for flexible protein-protein docking.
Type de document :
Article dans une revue
Computational Geometry, Elsevier, 2009
Liste complète des métadonnées

Littérature citée [28 références]  Voir  Masquer  Télécharger
Contributeur : Sebastien Loriot <>
Soumis le : jeudi 30 octobre 2008 - 17:39:54
Dernière modification le : vendredi 8 juin 2018 - 14:50:07
Document(s) archivé(s) le : mardi 9 octobre 2012 - 14:42:54


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


  • HAL Id : inria-00335866, version 1



Frédéric Cazals, Sebastien Loriot. Computing the Arrangement of Circles on a Sphere, with Applications in Structural Biology. Computational Geometry, Elsevier, 2009. 〈inria-00335866〉



Consultations de la notice


Téléchargements de fichiers