7
$\begingroup$

Bee swarm plots are a way of visualizing one-dimensional data sets, similar to box plots. The idea is that if there's not too many points (e.g. <300) we can just plot them along the $x$-axis with the $y$-offset chosen such that the points don't overlap, thus giving a "truthful" visual impression of the distribution. Sample image from https://seaborn.pydata.org/generated/seaborn.swarmplot.html: enter image description here

As far as I can tell, this library chooses the $y$-offset greedily, that is, it just plots the points in increasing order, and chooses the minimum (absolute) $y$-offset above or below the $x$-axis such that the circle marker does not overlap with any already plotted point. This leads to these "whiskers", which obscure the actual distribution of the data point. It would be nice to find an arrangement that is "optimal" in some sense. The most obvious formulation is:

Given $x_1, \dots, x_n$ find $y_1, \dots, y_n$ that minimizes $|y_1| + \cdots + |y_n|$ subject to $\text{dist}((x_i, y_i), (x_j, y_j)) > d$ for $i \neq j$, where $\text{dist}$ is Euclidean distance and $d$ is some constant (diameter of the circle markers).

This seems like a fairly basic problem, but I couldn't find anything about it in the literature. In particular I'm wondering whether it is NP-hard, and what approach might be feasible for optimally solving it. I tried an ILP formulation but it has extremely bad performance (can solve only ~40 points).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.