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
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
- Castalia and
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.
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.
hierarchical methods for the n-body problem, CS 267, Berkeley, 1995.
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
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.
Operations for Satellite Antenna Layout, J-D. Boissonnat, E. de
Lange, and M. Teillaud, SCG 1997.
n-body simulations using hierarchical octree representations of space.
based point pattern analysis methods for investigation of spatial
structure of various stellar populations, L. Pásztor, ADASS '94.
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.
Geometry in Action,
a collection of applications of computational geometry.
from a common source file.