%%% ====================================================================
%%% @LaTeX-file{
%%% filename = "callahank95.ltx",
%%% date = "20 November 1995",
%%% time = "21:41:30 EST",
%%% author = "David M. Jones",
%%% email = "jacm@theory.lcs.mit.edu",
%%% url = "http://theory.lcs.mit.edu/~jacm/",
%%% address = "Journal of the ACM
%%% MIT Laboratory for Computer Science
%%% Room NE43-316
%%% 545 Technology Square
%%% Cambridge, MA 02139
%%% USA",
%%% telephone = "(617) 253-5936",
%%% FAX = "(617) 253-3480",
%%% checksum = "09850 98 348 3138",
%%% codetable = "ISO/ASCII",
%%% supported = "yes",
%%% docstring = "Copyright (c) 1995 by ACM, Inc.
%%% Permission to make digital or hard copies of part
%%% or all of this work for personal or classroom use
%%% is granted without fee provided that copies are
%%% not made or distributed for profit or direct
%%% commercial advantage and that copies bear this
%%% notice and the full citation on the first page.
%%% Copyrights for components of this work owned by
%%% others than ACM must be honored. Abstracting with
%%% credit is permitted. To copy otherwise, to
%%% republish, to post on servers, or to redistribute
%%% to lists, requires prior specific permission
%%% and/or a fee. Request permissions from
%%% Publications Dept, ACM Inc., fax +1 (212)
%%% 869-0481, or permissions@acm.org.
%%%
%%% This is a LaTeX2e file. To process it, you will
%%% need a copy of the acmabs document class, which is
%%% available via the following URL:
%%%
%%% http://theory.lcs.mit.edu/~jacm/acmart/acmabs.cls
%%% ",
%%% }
%%% ====================================================================
\documentclass{acmabs}
\begin{document}
\Journal{Journal of the ACM}
\refkey{CallahanK95}
\title{A Decomposition of Multidimensional Point Sets with Applications to
{$k$}-Nearest-Neighbors and {$n$}-Body Potential Fields}
\author{Paul~B. Callahan \and S.~Rao Kosaraju}
\Pages{67--90}
\Month{January}
\Year{1995}
\Volume{42}
\Number{1}
\maketitle
\begin{abstract}
We define the notion of a \emph{well-separated pair decomposition} of points in
$d$-dimensional space. We then develop efficient sequential and parallel
algorithms for computing such a decomposition. We apply the resulting
decomposition to the efficient computation of $k$-nearest neighbors and
$n$-body potential fields.
\end{abstract}
\begin{categories}
F.2.2[geometrical problems and computation]; F.1.2[parallelism and concurrency]
\end{categories}
\begin{terms}
Algorithms, Theory
\end{terms}
\begin{keywords}
All nearest neighbors, fast multipole method
\end{keywords}
\end{document}