A Python Package for Well-Separated Pair Decomposition

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.

Keywords

• well-separated pair decomposition
• computational geometry