A Python Package for Well-Separated Pair Decomposition

Domagoj Matijević

doi:10.5334/jors.465

A Python Package for Well-Separated Pair Decomposition

Journal of Open Research Software

Volume 12 (2024): Issue 1

By: Domagoj Matijević

Open Access

|Jan 2024

Abstract

Well-separated pair decomposition (WSPD) is a well-known geometric decomposition used for encoding distances, introduced in 1995 by Paul B. Callahan and S. Rao Kosaraju in a seminal paper. We implemented this remarkable decomposition following the nontrivial algorithm for computing the partial fair split tree of a point set presented in the original article. Our implementation is done in C++. In addition to that, we made further effort to publish it as a Python package on PyPI. By doing so, we made our software easily accessible on Windows, Linux, or macOS to researchers and students worldwide.

References

Callahan PB, Kosaraju SR. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, jan 1995; 42(1): 67–90. ISSN 0004-5411. DOI: 10.1145/200836.200853
Open DOI Search in Google Scholar Back to article
Smid MHM. The well-separated pair decomposition and its applications. In Gonzalez TF (ed.), Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 2: Contemporary and Emerging Applications. Chapman and Hall/CRC; 2018.
Search in Google Scholar Back to article
Narasimhan G, Smid MHM. Geometric spanner networks. Cambridge University Press; 2007. DOI: 10.1017/CBO9780511546884
Open DOI Search in Google Scholar Back to article
Klein R. Well Separated Pair Decomposition. New York, NY: Springer New York, 2016; 2368–2371. ISBN 978-1-4939-2864-4. DOI: 10.1007/978-1-4939-2864-4_479
Open DOI Search in Google Scholar Back to article
Wang Y, Yu S, Dhulipala L, Gu Y, Shun J. Pargeo: A library for parallel computational geometry. In Proceedings of the 27th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’22. New York, NY, USA, 2022; 450–452. Association for Computing Machinery. ISBN 9781450392044. DOI: 10.1145/3503221.3508429
Open DOI Search in Google Scholar Back to article
Jakob W, Rhinelander J, Moldovan D. pybind11 – seamless operability between c++11 and python; 2017. https://github.com/pybind/pybind11.
Search in Google Scholar Back to article
Github actions documentation. URL: https://docs.github.com/en/actions.
Search in Google Scholar Back to article
Python package index pypi. URL: https://pypi.org/.
Search in Google Scholar Back to article
Beier R, Funke S, Matijević D, Sanders P. Energy-efficient paths in radio networks. Algorithmica, oct 2011; 61(2): 298–319. ISSN 0178-4617. DOI: 10.1007/s00453-010-9414-0
Open DOI Search in Google Scholar Back to article