Astronomy

Computational geometry problems arise in astronomy in observation planning, shape reconstruction for irregular bodies such as asteroids, clustering for galaxy distribution analysis, and hierarchical decomposition of point sets for n-body simulations.

• Applications of the linear quadtree to astronomical databases, P. Barrett, NASA. Encoding astronomical coordinates with quadtrees can provide significant improvements in efficiency when accessing sources near a given direction and can aid in the correlation of positions from different astronomical catalogs.

• Castalia and Deimos. Philip Stook at U. Western Ontario mentions an application of 3d convex hulls in mapping the surfaces of these two asteroids.

• Computer science and astrophysics, R. Anderson.

• Cosmology at the University of Kentucky. This group works on large-scale structure formation, using methods including N-body simulations and minimum spanning trees.

• Data Collection for the Sloan Digital Sky Survey - A Network Flow Heuristic, Robert Lupton, F. Miller Maley, and Neal E. Young, SODA '96, describes a planar clustering problem arising in planning the telescope positions for a sky survey, and gives a heuristic solution.

• Fast hierarchical methods for the n-body problem, CS 267, Berkeley, 1995.

• Finding quasar superstructures. M. Graham and co-authors use 2d and 3d minimum spanning trees for finding clusters of quasars and Seyfert galaxies.

• Galaxy formation with n-body simulations. J. K. Salmon et al. study galaxy formation by simulating systems of roughly 10^7 particles, using codes based on a k-D-tree-like recursive orthogonal partition.

• Inverse nearest neighbors for astrophysical N-body simulations, R. Anderson, M. Cary, and B. Tjaden, U. Washington.

• A minimal spanning tree analysis of the CfA redshift survey. Dan Lauer uses minimum spanning trees to understand the large-scale structure of the universe.

• Minkowski Operations for Satellite Antenna Layout, J-D. Boissonnat, E. de Lange, and M. Teillaud, SCG 1997.

• Parallel n-body simulations using hierarchical octree representations of space.

• Partition based point pattern analysis methods for investigation of spatial structure of various stellar populations, L. Pásztor, ADASS '94.

• The Well-Separated Pair Decomposition and its Applications, Paul Callahan's Johns Hopkins Ph.D. thesis on hierarchical space decomposition and its applications to n-body simulation.