## 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.

Part of
Geometry in Action,
a collection of applications of computational geometry.

David Eppstein,
Theory Group,
ICS,
UC Irvine.

Semi-automatically
filtered
from a common source file.