Parallelization of Particle Methods on the Sphere

We consider data structures and algorithms for efficient parallelization ofparticle methods when the domain is the surface of a sphere. Such applicationstypically arise when dealing with directional data. We propose a domaindecomposition scheme based on a combination of geometric and combinatorialpartitioning, that provides domains suitable for efficient implementation ofrequisite operations that are performed on the data in parallel. The algorithmhas the advantage of being fast enough to be applied dynamically, and at thesame time provides good partitions, comparable in quality to those produced bymultilevel graph partitioning schemes.