Introduction

Many different problems in geometry involve Euclidean distances defined by pairs of n points in a given point set. For example, the closest pair problem, the all-nearest-neighbors problem, the problem of determining k smallest distances among $(\begin{array}{c}n\\ 2\end{array})$M2 \documentclass[10pt]{article} \usepackage{wasysym} \usepackage[substack]{amsmath} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage[mathscr]{eucal} \usepackage{mathrsfs} \usepackage{pmc} \usepackage[Euler]{upgreek} \pagestyle{empty} \oddsidemargin -1.0in \begin{document} \[(\begin{array}{*{20}{c}} n\\ 2 \end{array})\] \end{document} pairwise distances, etc. The solution to such problems often relies on some ‘clever’ search over a quadratic space of pairwise distances. The natural question is whether one can efficiently approximate the space of pairwise distances in subquadratic space and, by doing so, help provide an efficient solution to many of the problems mentioned above. The answer to that question was given in a seminal work by Paul B. Callahan and S. Rao Kosaraju in 1995 ([1]), which showed that the quadratic space of all pairwise distances could be encoded in O(n) space and O(n log n) construction time, for a fixed dimension d. The decomposition they introduced is well-separated pair decomposition (WSPD), a well-known decomposition in computational geometry.

Many exact and approximate algorithms for different proximity problems are based on a WSPD: the diameter problem, the spanner problem, the minimum spanning tree, etc. (for the complete list of problems, see [2]). An extensive overview of the a WSPD and its applications is given in the book [3]. A WSPD has even been listed among problems in the Encyclopedia of Algorithms ([4]), which presents solutions to the most important algorithmic problems. Surprisingly, no efficient implementation of a WSPD can be found in public software libraries available for students and researchers.

This paper presents the software package that implements a WSPD following the nontrivial algorithm of the partial fair-split tree presented in [1] that guarantees the construction time of O (n log n) and a WSPD of O(n) size. To our knowledge, our implementation is the first open-source and publicly available implementation of WSPD that carefully follows the original algorithm in [1]. Recently published implementation of a WSPD in ParGeo C++ library (see [5]) uses simple fair-split kdtree and does not ensure theoretic bounds on the size of a WSPD.

Moreover, in order to make it convenient for researchers and students and available for everyday use, we created Python bindings to our C++ code and published it to PyPI. Python module can be run on Windows, macOS, and Linux for all Python versions starting from 3.7.

Implementation and architecture

The implementation of a WSPD was done in C++ with the help of STL containers, and no other external libraries were used. To facilitate the practical use of our software, we used the pybind11 library ([6]) to enable Python binding to our C++ implementation. The main advantage of pybind11 is that it allows for automatic conversion between STL containers and Python list, set, and dict data structures. More precisely, we use native Python types <int, int, float, list> in Python function wspd.build_wspd(), and pybind11 converts them to native C++ types <int, int, double, stl::vector> in the corresponding C++ function call. In the opposite direction, the well-separated pairs of a WSPD, once computed in C++, are represented as a composite data type

<stl::vector<stl::pair<stl::vector<int>, stl::vector<int>>>>

and pybind11 converts them to Python’s list<tupe<list, list>>. Type conversions involve copying data during Python/C++ transitions due to memory layout differences. We direct the interested reader to pybind documentation (see [6]) for more details about type conversions.

Furthermore, we used the GitHub Actions CI/CD [7] to compile our project for Windows, Linux, and macOS and released it as a Python package on the Python Package Index PyPI [8] platform.

Quality control

Tests for the WSPD package are performed using different-sized random data and manually constructed inputs where the correct results are known. In Figure 1, left, one can see that our implementation outputs well-separated pairs typically in less than a few seconds for inputs as large as 20 000 points in the plane. Unfortunately, the dependence in the running time on the dimension is exponential, which is also reflected in our experiments. In Figure 1, right, we revealed the total number of well-separated pairs as a function of the input size. Surprisingly, the compression ratio, i.e., the total number of well-separated pairs of sets divided by the total number of pairwise distances n·(n–1)/2, decreases in practice as the size of the input set of points increases. Thus, the larger the space of all pairwise distances, the better it gets compressed with the WSPD algorithm.

Operating system

The package is platform-independent and it can be run on Linux, macOS and Windows.

Programming language

Python versions 3.7 and larger. The software can also be included in other C++ projects.

Additional system requirements

None

Dependencies

WSPD is implemented in C++ and uses only standard STL containers and C++ native types. No dependencies on the Python side are required. However, for visualizing a WSPD, you might want to use matplotlib, and for point set generation, you might want to rely on numpy random sampling.

Software location

Language

English

Use case for the software

Figure 2 shows a WSPD computed on a simple example.¹ Though the example is elementary and comprises only eight different points, it already demonstrates the effectiveness of pairwise distance compression, e.g., note that all possible pairwise distances among any number of points placed in different red rectangles are already all efficiently approximated by pairwise distances between red rectangles.

For Python users, installing the WSPD module now amounts to a simple pip install wspd command. In the following, we provide a simple example of how the WSPD package can be used, following the example depicted in Figure 2.

import wspd
data_pts = [(1,0),(2,1),(1,10),(2,9),(10,4),(11,5),(5,4),(5.5,3.5)]
nr_pts = len(data_pts) # number of points
dim = len(data_pts[0]) # point dimension
# move points from Python list to point class objects
data_pts = [wspd.point(p) for p in data_pts]
# compute WSPD and return well-separated pairs
dumbbells = wspd.build_wspd(nr_pts, dim, S, data_pts)

As already stated, a well-separated pair decomposition has an application in solving a number of problems. For example, given the well-separated sequence (A₁, B₁)… (A_k, B_k) computed by the build_wspd() function, the closest pair problem can be computed in an additional O(n) time by a simple inspection of all pairs (A_j, B_j), 1 ≤ j ≤ k, where both A_j and B_j are singleton sets. A similar approach can be used to compute the k closest pairs problem or for many approximate proximity problems (for the complete list of proximity problems, a WSPD has the direct consequence to, see [2]). Finally, it is worth mentioning that a WSPD has been successfully used in different geometric problems, e.g., the computation of energy-efficient paths in radio networks [9]. A well-separated pairs were used for the precomputation of ‘template’ paths that were further used in the query phase of their algorithm.

In conclusion, a well-separated pair decomposition is a powerful technique that has proven useful in various applications in geometry. We hope that this open-source project could also lead to further collaboration, as other researchers may contribute improvements and new features to this Python package over time.