Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadatas

Cited literature [37 references]  Display  Hide  Download
Contributor : Frederic Cazals <>
Submitted on : Tuesday, September 18, 2007 - 8:36:35 PM
Last modification on : Saturday, January 27, 2018 - 1:30:59 AM
Long-term archiving on: : Monday, October 22, 2012 - 2:30:38 PM


Files produced by the author(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⟩



Record views


Files downloads