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

ABSTRACT

The Bentley-Ottmann (BO) algorithm, initially designed to report theintersection points of line-segments in the plane, is the prototypicalsweep-line algorithm. This video presents an extension of the BOalgorithm to the spherical setting, so as to compute the exactarrangement of a collection of circles on a sphere.An application in bio-chemistry, geared towards the investigation ofatomic environments and multi-body interactions in macro-molecules, isalso presented.The reader is referred toRef. [1] for the companion paper of this video.

REFERENCES

• 1: F. Cazals and S. Loriot. Computing the exact arrangement of circles on a sphere, with applications in structural biology. Research Report 6049, INRIA, 2006. https://hal.inria.fr/inria-00118781
• 2: F. Cazals, S. Loriot, P. Machado, and M. Teillaud. Design of the CGAL 3D spherical kernel. In preparation.
• 3: F. Cazals, F. Proust, R. Bahadur, and J. Janin. Revisiting the voronoi description of protein-protein interfaces. Protein Science, 15(9):2082--2092, 2006.
• 4: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING

General Terms:
Algorithms, Experimentation

Keywords:
Van der Waals models, arrangements, molecular surfaces, robust geometric software, structural biology