  As galaxy surveys become larger and more complex, keeping track of the
completeness, magnitude limit, and other survey parameters as a function of
direction on the sky becomes an increasingly challenging computational task.
For example, typical angular masks of the Sloan Digital Sky Survey contain
about N=300,000 distinct spherical polygons. Managing masks with such large
numbers of polygons becomes intractably slow, particularly for tasks that run
in time O(N^2) with a naive algorithm, such as finding which polygons overlap
each other. Here we present a "divide-and-conquer" solution to this challenge:
we first split the angular mask into predefined regions called "pixels," such
that each polygon is in only one pixel, and then perform further computations,
such as checking for overlap, on the polygons within each pixel separately.
This reduces O(N^2) tasks to O(N), and also reduces the important task of
determining in which polygon(s) a point on the sky lies from O(N) to O(1),
resulting in significant computational speedup. Additionally, we present a
method to efficiently convert any angular mask to and from the popular HEALPix
format. This method can be generically applied to convert to and from any
desired spherical pixelization. We have implemented these techniques in a new
version of the mangle software package, which is freely available at
http://space.mit.edu/home/tegmark/mangle/, along with complete documentation
and example applications. These new methods should prove quite useful to the
astronomical community, and since mangle is a generic tool for managing angular
masks on a sphere, it has the potential to benefit terrestrial mapmaking
applications as well.
