We describe an O(n^d) time algorithm for computing the exact probability that two d-dimensional probabilistic point sets are linearly separable, for any fixed d >= 2. A probabilistic point in d-space is the usual point, but with an associated (independent) probability of existence. We also show that the d-dimensional separability problem is equivalent to a (d+1)-dimensional convex hull membership problem, which asks for the probability that a query point lies inside the convex hull of n probabilistic points. Using this reduction, we improve the current best bound for the convex hull membership by a factor of n [Agarwal et al., ESA, 2014]. In addition, our algorithms can handle "input degeneracies" in which more than k+1 points may lie on a k-dimensional subspace, thus resolving an open problem in [Agarwal et al., ESA, 2014]. Finally, we prove lower bounds for the separability problem via a reduction from the k-SUM problem, which shows in particular that our O(n^2) algorithms for 2-dimensional separability and 3-dimensional convex hull membership are nearly optimal.

Storyline visualizations help visualize encounters of the characters in a story over time. Each character is represented by an x-monotone curve that goes from left to right visualizing progression of time. A meeting is represented by having the characters that participate in the meeting run close together for some time. In order to keep the visual complexity low, rather than just minimizing pairwise crossings of curves, we propose to count block crossings, that is, pairs of intersecting bundles of lines. In a block crossing, two blocks of parallel lines intersect each other, which is less distracting than the same number of individual crossings being spread over the drawing. In this paper, we show that minimizing the number of block crossings is NP-hard, even if all meetings are of size 2. For this special case, we present a greedy heuristic, which we evaluate experimentally. We show that the general case is fixed-parameter tractable. Our main results is a constant-factor approximation algorithm for meetings of bounded size. The algorithm is based on (approximately) solving a hyperedge deletion problem on hypergraphs that may be of independent interest.

Scatter plots are diagrams that visualize two-dimensional data as sets of points in the plane. They allow users to detect correlations and clusters in the data. Whether or not a user can accomplish these tasks highly depends on the aspect ratio selected for the plot, i.e., the ratio between the horizontal and the vertical extent of the diagram. We argue that an aspect ratio is good if the Delaunay triangulation of the scatter plot at this aspect ratio has some nice geometric property, e.g., a large minimum angle or a small total edge length. More precisely, we consider the following optimization problem. Given a set Q of points in the plane, find a scale factor s such that scaling the x-coordinates of the points in Q by s and the y-coordinates by 1=s yields a point set P(s) that optimizes a property of the Delaunay triangulation of P(s), over all choices of s. We present an algorithm that solves this problem efficiently and demonstrate its usefulness on real-world instances. Moreover, we discuss an empirical test in which we asked 64 participants to choose the aspect ratios of 18 scatter plots. We tested six different quality measures that our algorithm can optimize. In conclusion, minimizing the total edge length and minimizing what we call the 'uncompactness' of the triangles of the Delaunay triangulation yielded the aspect ratios that were most similar to those chosen by the participants in the test.

In this paper, we investigate the problem of labeling point sites in focus regions of maps or diagrams. This problem occurs, for example, when the user of a mapping service wants to see the names of restaurants or other POIs in a crowded downtown area but keep the overview over a larger area. Our approach is to place the labels at the boundary of the focus region and connect each site with its label by a linear connection, which is called a leader. In this way, we move labels from the focus region to the less valuable context region surrounding it. In order to make the leader layout well readable, we present algorithms that rule out crossings between leaders and optimize other characteristics such as total leader length and distance between labels. This yields a new variant of the boundary labeling problem, which has been studied in the literature. Other than in traditional boundary labeling, where leaders are usually schematized polylines, we focus on leaders that are either straight-line segments or Bezier curves. Further, we present algorithms that, given the sites, find a position of the focus region that optimizes the above characteristics. We also consider a variant of the problem where we have more sites than space for labels. In this situation, we assume that the sites are prioritized by the user. Alternatively, we take a new facility-location perspective which yields a clustering of the sites. We label one representative of each cluster. If the user wishes, we apply our approach to the sites within a cluster, giving details on demand.