article

Free access

A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields

Authors:

Paul B. Callahan,

S. Rao KosarajuAuthors Info & Claims

Journal of the ACM (JACM), Volume 42, Issue 1

Pages 67 - 90

https://doi.org/10.1145/200836.200853

Published: 03 January 1995 Publication History

Abstract

We define the notion of a 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.

References

[1]

~AARSETH, S. J., GOTr, J. R., III, AND TURNER, E. L. 1979. N-body simulations of galaxy ~clustering. I. Initial conditions and galaxy collapse times. Astrophys. J. 228, 664-683.

[2]

~ABRAHAMSON, K., DADOUN, N., KIRKPATRICK, D. A., AND PRZYTCHKA, T. 1989. A simple parallel ~tree contraction algorithm. J. Algorithms 10, 2, 287-302.

[3]

~ABRAMSON, N. 1963. Information Theory and Coding. McGraw-Hill, New York.

[4]

~AGARWAL, P. K., EDELSBRUNNER, H., SCHWARTZKOPF, O., AND WELZL, E. 1991. Euclidean ~minimum spanning trees and bichromatic closest pairs. Disc. Computat. Geom. 6, 407-422.

[5]

~AGARWAL, P. K., AND MATOU~EK, J. 1992. Relative neighborhood graphs in three dimensions. In ~Proceedings of the 3rd Annual Sympostum on Discrete Algorithms. ACM-SIAM, New York and ~Philadelphia, pp. 58-65.

[6]

~APPEL, A. W. 1985. An efficient program for many-body simulation. SIAM J. Sci. Star. Comput. ~6, 85-103.

[7]

~BARNES, J., AND HUT, P. 1986. A hierarchical O(N log N) force-calculation algorithm. Nature ~~ 324, 4, 446-449.

[8]

~BENTLEY, J. L. 1980. Multidimensional divide-and-conquer. Commun. ACM 23, 4 (Apr), 214-229.

[9]

~CALLAHAN, P. B., AND KOSAP, AJU, S. R. 1992. A decomposition of multi-dimensional point-sets ~with applications to k-nearest-neighbors and n-body potential fields. In Proceedings of the 24th ~Annual Symposium on the Theory of Computing (Victoria, B. C., Canada, May 4-6). ACM, New ~York, pp. 546-556.

[10]

~COLE, R., AND GOODRICH, M. T. 1988. Optimal parallel algorithms for polygon and point-set ~problems. In Proceedings of the 4th ACM Symposium on Computational Geometry (Urbana- ~Champaign, IlL, June 6-8). ACM, New York, pp. 201-210.

[11]

~COLE, R., AND GOODRICH, M. T. 1992. Optimal parallel algorithms for point-set and polygon ~problems. Algorithmica 7, 3-23.

[12]

~FRIEZE, A. M., MILLER, G. L., AND TENG, S.-H. 1992. Separator based parallel divide and ~Algorithms andArch~tectures (San Diego, Calif., June 29-July 1). ACM, New York, pp. 420-429.

[13]

~OAZIT, H., MILLER, O. L., AND TENG, S.-H. 1988. Optimal tree contraction in the EREW model. ~In Concurrent Computations, S. K. Tewsburg, B. W. Dickinson, and S. C. Schwartz, eds. Plenum ~Publishing, New York, pp. 139-155.

[14]

~GREENGARD, L. F. 1988. The Rapid Evaluation of Potential Ftelds in Particle Systems. The MIT ~Press, Cambridge, Mass.

[15]

~GREENGARD, L., AND GROPP, W. D. 1990. A parallel version of the fast multipole method ~Computers Math. Applic. 20, 7, 63-71.

[16]

~GREENGARD, m., AND ROKHLIN, V. 1987. A fast algorithm for particle simulations, J. Comput ~Physics 73, 325-348.

[17]

~HAFNER, C., AND mUSTER, N. 1991. Computations of electromagnetic fields by the multiple ~multipole method (generalized multipole technique). Radio Sci. 26, 1, 291-297.

[18]

~KATZENELSON, J. 1989. Computational structure of the N-body problem. SIAM J. Sci. Star ~Comput. 10, 4 (July), 787-815.

[19]

~KOSARAJU, S. R., AND DELCHER, A. L. 1988. Optimal parallel evaluation of tree-structured ~computations by raking. In VLSI Algorithms and Architectures: Proceedings of the 3rd Aegean ~Workshop on Computing, J. Reif, ed. Springer-Verlag, New York, pp. 101-110.

[20]

~MILLER, G. L., TENG, S.-H. AND VAVASIS, S. A. 1991. A unified geometric approach to graph ~separators. In Proceedings of the 32nd Annual Symposium on Foundatzons Computer Science ~IEEE, New York, pp. 538-547.

[21]

~MILLER, R. H., AND PRENDERGAST, K. H. 1968. Stellar dynamics in a discrete phase space ~Astrophys. J. 151, 699-709.

[22]

~MILLER, R. H., PRENDERGAST, K. H. AND QUIRK, W. J. 1970. Numerical experiments on spiral ~structure. Astrophys. J. 161, 903 916.

[23]

~PAN, V. Y., REIF, J. H., AND TATE, S. R. 1992. The power of combining the techniques oJ ~algebraic and numerical computing: Improved approximate multipoint polynomial evaluation ~and improved multipole algorithms. In Proceedings of the 32nd Annual Symposium of Founda- ~ttons of Computer Science. IEEE New York, pp. 703-7t3.

[24]

~PREPARATA, F. P., AND SHAMOS, M. I. 1985. Computational Geometry. An Introduction. Springer- ~Verlag, New York.

[25]

~REIF, J. H., AND TARE, S. R. 1992. N-body simulation I: Potential field evaluation. Technical ~report, Comput. Sci. Dept., Duke Univ.

[26]

~ROKHL1N, V. 1985. Rapid solution of integral equations of classical potential theory. J. Compu- ~tat. Phys. 60, 187-207.

[27]

~SCHMIDT, K. E., AND LEE, M. m. 1991. Implementing the fast multipole method in three ~dimensions. J. Star. Phys. 63 5-6 (June), 1223-1235.

[28]

~VAIDYA, P. M. 1986. An optimal algorithm for the all-nearest-neighbors problem. In Proceedin&, ~of the 27th Annual Sympostum Foundations of Computer Science. IEEE, New York, pp. 117-122

[29]

~AIDYA, P. M. 1989. An O(n log n) algorithm for the all-nearest-neighbors problem. Disc ~omputat. Geom. 4, 101-115.

[30]

~YAO, A. C. 1982. On constructing minimum spanning trees in k-dimensional space and related ~problems. SIAM J. Comput. 11,721-736.

[31]

~ZHAO, F., AND JOHNSSON, S. L. 1991. The parallel multipole method on the Connection ~Machine. SIAM J. Sct. Stat. Comput. 12, 6, 1420-1437.

Cited By

Farhana TKatz M(2025)Spanners under the Hausdorff and Fréchet distancesInformation Processing Letters10.1016/j.ipl.2024.106513187:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.ipl.2024.106513
Matijević D(2024)A Python Package for Well-Separated Pair DecompositionJournal of Open Research Software10.5334/jors.46512Online publication date: 2-Jan-2024
https://doi.org/10.5334/jors.465
Drake MFefferman CRen KSkorobogatova A(2024)Sobolev extension in a simple caseAdvanced Nonlinear Studies10.1515/ans-2023-0132Online publication date: 24-May-2024
https://doi.org/10.1515/ans-2023-0132
Show More Cited By

Index Terms

A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields
1. Computing methodologies
  1. Parallel computing methodologies
    1. Parallel algorithms
2. Theory of computation

Recommendations

A decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version)
STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of Computing

We define the notion of a well-separated pair decomposition of points in d-dimensional space. We develop efficient sequential and parallel algorithms for computing such a decomposition. We apply the resulting decomposition to the efficient computation ...
Extending LAESA Fast Nearest Neighbour Algorithm to Find the k Nearest Neighbours
Proceedings of the Joint IAPR International Workshop on Structural, Syntactic, and Statistical Pattern Recognition

Many pattern recognition tasks make use of the k nearest neighbour (k-NN) technique. In this paper we are interested on fast k- NN search algorithms that can work in any metric space i.e. they are not restricted to Euclidean-like distance functions. ...
λ-Diverse Nearest Neighbors Browsing for Multidimensional Data

Traditional search methods try to obtain the most relevant information and rank it according to the degree of similarity to the queries. Diversity in query results is also preferred by a variety of applications since results very similar to each other ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 42, Issue 1

Jan. 1995

289 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/200836

Issue’s Table of Contents

Copyright © 1995 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1995

Published in JACM Volume 42, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

363
Total Citations
View Citations
2,557
Total Downloads

Downloads (Last 12 months)235
Downloads (Last 6 weeks)27

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Farhana TKatz M(2025)Spanners under the Hausdorff and Fréchet distancesInformation Processing Letters10.1016/j.ipl.2024.106513187:COnline publication date: 1-Jan-2025
https://dl.acm.org/doi/10.1016/j.ipl.2024.106513
Matijević D(2024)A Python Package for Well-Separated Pair DecompositionJournal of Open Research Software10.5334/jors.46512Online publication date: 2-Jan-2024
https://doi.org/10.5334/jors.465
Drake MFefferman CRen KSkorobogatova A(2024)Sobolev extension in a simple caseAdvanced Nonlinear Studies10.1515/ans-2023-0132Online publication date: 24-May-2024
https://doi.org/10.1515/ans-2023-0132
Bhore STóth C(2024)Online Euclidean SpannersACM Transactions on Algorithms10.1145/368179021:1(1-22)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3681790
Yan YWong R(2024)Proximity Queries on Point Clouds using Rapid Construction Path OracleProceedings of the ACM on Management of Data10.1145/36392612:1(1-26)Online publication date: 26-Mar-2024
https://dl.acm.org/doi/10.1145/3639261
Wei VWong RLong CMount DSamet H(2024)On Efficient Shortest Path Computation on Terrain Surface: A Direction-Oriented ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336314736:8(4129-4143)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3363147
Berner LErwerle JFunke SProissl CRieg FStorandt S(2024)Improved Lightweight Rendering of Road Networks based on Contraction Hierarchies2024 IEEE 17th Pacific Visualization Conference (PacificVis)10.1109/PacificVis60374.2024.00030(202-211)Online publication date: 23-Apr-2024
https://doi.org/10.1109/PacificVis60374.2024.00030
Nie C(2024)Differentiate data by higher-order structuresInformation Sciences: an International Journal10.1016/j.ins.2023.119882655:COnline publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1016/j.ins.2023.119882
Bose PTuttle T(2024)Routing on heavy path WSPD spannersComputational Geometry: Theory and Applications10.1016/j.comgeo.2024.102121123:COnline publication date: 1-Dec-2024
https://dl.acm.org/doi/10.1016/j.comgeo.2024.102121
Poureidi AFarshi M(2024)On algorithmic complexity of imprecise spannersComputational Geometry: Theory and Applications10.1016/j.comgeo.2023.102051117:COnline publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1016/j.comgeo.2023.102051
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents