A Framework for Algorithm Stability
W. Meulemans, B. Speckmann, K.A.B. Verbeek, and J. Wulms.
arXiv,
2017.
－ Abstract
We say that an algorithm is stable if small changes in the input result in small changes in the output. Algorithm stability plays an important role when analyzing and visualizing time-varying data. However, so far, there are only few theoretical results on the stability of algorithms, possibly due to a lack of theoretical analysis tools. In this paper we present a framework for analyzing the stability of algorithms. We focus in particular on the tradeoff between the stability of an algorithm and the quality of the solution it computes. Our framework allows for three types of stability analysis with increasing degrees of complexity: event stability, topological stability, and Lipschitz stability. We demonstrate the use of our stability framework by applying it to kinetic Euclidean minimum spanning trees.
－ BibTeX
@article{a-framework-for-algorithm-stability:2017,
title = {A Framework for Algorithm Stability},
author = {W. Meulemans and B. Speckmann and K.A.B. Verbeek and J. Wulms},
year = {2017},
bookTitle = {arXiv},
}
[ PDF ]
Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments
A. Igamberdiev, W. Meulemans, and A. Schulz.
Journal of Graph Algorithms and Applications,
21(4):561—588,
2017.
－ Abstract
A drawing of a graph can be understood as an arrangement of geometric objects. In the most natural setting the arrangement is formed by straight-line segments. Every cubic planar 3-connected graph with n<br/>n<br/> vertices has such a drawing with only n/2+3<br/>n/2+3<br/> segments, matching the lower bound. This result is due to Mondal et al. [J. of Comb. Opt., 25], who gave an algorithm for constructing such drawings. We introduce two new algorithms that also produce drawings with n/2+3<br/>n/2+3<br/> segments. One algorithm is based on a sequence of dual edge contractions, the other is based on a recursion of nested cycles. We also show a flaw in the algorithm of Mondal et al. and present a fix for it. We then compare the performance of these three algorithms by measuring angular resolution, edge length and face aspect ratio of the constructed drawings. We observe that the corrected algorithm of Mondal et al. mostly outperforms the other algorithms, especially in terms of angular resolution. However, the new algorithms perform better in terms of edge length and minimal face aspect ratio.
－ BibTeX
@article{drawing-planar-cubic-3-connected-graphs-with-few-segments-algorithms-amp-experiments:2017,
title = {Drawing Planar Cubic 3-Connected Graphs with Few Segments: Algorithms & Experiments},
author = {A. Igamberdiev and W. Meulemans and A. Schulz},
year = {2017},
bookTitle = {Journal of Graph Algorithms and Applications},
}
Drawing Planar Graphs with Few Geometric Primitives
G. Hültenschmidt, P. Kindermann, W. Meulemans, and A. Schulz.
arXiv,
pp. 1—18,
2017.
－ Abstract
We define the emph{visual complexity of a plane graph drawing to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw two collinear edges of the same vertex). Let n denote the number of vertices of a graph. We show that trees can be drawn with 3n/4 straight-line segments on a polynomial grid, and with n/2 straight-line segments on a quasi-polynomial grid. Further, we present an algorithm for drawing planar 3-trees with (8n−17)/3 segments on an O(n)×O(n 2 ) grid. This algorithm can also be used with a small modification to draw maximal outerplanar graphs with 3n/2 edges on an O(n)×O(n 2 ) grid. We also study the problem of drawing maximal planar graphs with circular arcs and provide an algorithm to draw such graphs using only (5n−11)/3 arcs. This provides a significant improvement over the lower bound of 2n for line segments for a nontrivial graph class.
－ BibTeX
@article{drawing-planar-graphs-with-few-geometric-primitives:2017,
title = {Drawing Planar Graphs with Few Geometric Primitives},
author = {G. Hültenschmidt and P. Kindermann and W. Meulemans and A. Schulz},
year = {2017},
bookTitle = {arXiv},
}
[ PDF ]
Experimental Analysis of the Accessibility of Drawings with Few Segments
P. Kindermann, W. Meulemans, and A. Schulz.
arXiv,
pp. 1—14,
2017.
－ Abstract
The visual complexity of a graph drawing is defined as the number of geometric objects needed to represent all its edges. In particular, one object may represent multiple edges, e.g., one needs only one line segment to draw two collinear incident edges. We study the question if drawings with few segments have a better aesthetic appeal and help the user to asses the underlying graph. We design an experiment that investigates two different graph types (trees and sparse graphs), three different layout algorithms for trees, and two different layout algorithms for sparse graphs. We asked the users to give an aesthetic ranking on the layouts and to perform a furthest-pair or shortest-path task on the drawings.
－ BibTeX
@article{experimental-analysis-of-the-accessibility-of-drawings-with-few-segments:2017,
title = {Experimental Analysis of the Accessibility of Drawings with Few Segments},
author = {P. Kindermann and W. Meulemans and A. Schulz},
year = {2017},
bookTitle = {arXiv},
}
[ PDF ]
Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance
K.A. Buchin, M. Buchin, W. Meulemans, and W. Mulzer.
Discrete and Computational Geometry,
58(1):180—216,
2017.
－ Abstract
Given two polygonal curves in the plane, there are many ways to define a notion of similarity between them. One popular measure is the Fréchet distance. Since it was proposed by Alt and Godau in 1992, many variants and extensions have been studied. Nonetheless, even more than 20 years later, the original O(n 2 logn)
O(n2logn)
algorithm by Alt and Godau for computing the Fréchet distance remains the state of the art (here, n denotes the number of edges on each curve). This has led Helmut Alt to conjecture that the associated decision problem is 3SUM-hard. In recent work, Agarwal et al. show how to break the quadratic barrier for the discrete version of the Fréchet distance, where one considers sequences of points instead of polygonal curves. Building on their work, we give a randomized algorithm to compute the Fréchet distance between two polygonal curves in time O(n 2 logn − − − − √ (loglogn) 3/2 )
O(n2logn(loglogn)3/2)
on a pointer machine and in time O(n 2 (loglogn) 2 )
O(n2(loglogn)2)
on a word RAM. Furthermore, we show that there exists an algebraic decision tree for the decision problem of depth O(n 2−ε )
O(n2−ε)
, for some ε>0
ε>0
. We believe that this reveals an intriguing new aspect of this well-studied problem. Finally, we show how to obtain the first subquadratic algorithm for computing the weak Fréchet distance on a word RAM.
－ BibTeX
@article{four-soviets-walk-the-dog-improved-bounds-for-computing-the-fr-chet-distance:2017,
title = {Four Soviets Walk the Dog: Improved Bounds for Computing the Fréchet Distance},
author = {K.A. Buchin and M. Buchin and W. Meulemans and W. Mulzer},
year = {2017},
bookTitle = {Discrete and Computational Geometry},
}
[ PDF ]
Map LineUps: Effects of Spatial Structure on Graphical Inference
Roger Beecham, Jason Dykes, Wouter Meulemans, Aidan Slingsby, Cagatay Turkay, and Jo Wood.
IEEE Transactions on Visualization and Computer Graphics,
23(1):391—400,
2017.
－ Abstract
Fundamental to the effective use of visualization as an analytic and descriptive tool is the assurance that presenting data visually provides the capability of making inferences from what we see. This paper explores two related approaches to quantifying the confidence we may have in making visual inferences from mapped geospatial data. We adapt Wickham et al.'s `Visual Line-up' method as a direct analogy with Null Hypothesis Significance Testing (NHST) and propose a new approach for generating more credible spatial null hypotheses. Rather than using as a spatial null hypothesis the unrealistic assumption of complete spatial randomness, we propose spatially autocorrelated simulations as alternative nulls. We conduct a set of crowdsourced experiments (n=361) to determine the just noticeable difference (JND) between pairs of choropleth maps of geographic units controlling for spatial autocorrelation (Moran's I statistic) and geometric configuration (variance in spatial unit area). Results indicate that people's abilities to perceive differences in spatial autocorrelation vary with baseline autocorrelation structure and the geometric configuration of geographic units. These results allow us, for the first time, to construct a visual equivalent of statistical power for geospatial data. Our JND results add to those provided in recent years by Klippel et al. (2011), Harrison et al. (2014) and Kay & Heer (2015) for correlation visualization. Importantly, they provide an empirical basis for an improved construction of visual line-ups for maps and the development of theory to inform geospatial tests of graphical inference.
－ BibTeX
@article{map-lineups-effects-of-spatial-structure-on-graphical-inference:2017,
title = {Map LineUps: Effects of Spatial Structure on Graphical Inference},
author = {Roger Beecham and Jason Dykes and Wouter Meulemans and Aidan Slingsby and Cagatay Turkay and Jo Wood},
year = {2017},
bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
}
[ PDF ]
Small Multiples with Gaps
W. Meulemans, J. Dykes, A. Slingsby, C. Turkay, and J. Wood.
IEEE Transactions on Visualization and Computer Graphics,
23(1):381—390,
2017.
－ Abstract
Small multiples enable comparison by providing different views of a single data set in a dense and aligned manner. A common frame defines each view, which varies based upon values of a conditioning variable. An increasingly popular use of this technique is to project two-dimensional locations into a gridded space (e.g. grid maps), using the underlying distribution both as the conditioning variable and to determine the grid layout. Using whitespace in this layout has the potential to carry information, especially in a geographic context. Yet, the effects of doing so on the spatial properties of the original units are not understood. We explore the design space offered by such small multiples with gaps. We do so by constructing a comprehensive suite of metrics that capture properties of the layout used to arrange the small multiples for comparison (e.g. compactness and alignment) and the preservation of the original data (e.g. distance, topology and shape). We study these metrics in geographic data sets with varying properties and numbers of gaps. We use simulated annealing to optimize for each metric and measure the effects on the others. To explore these effects systematically, we take a new approach, developing a system to visualize this design space using a set of interactive matrices. We find that adding small amounts of whitespace to small multiple arrays improves some of the characteristics of 2D layouts, such as shape, distance and direction. This comes at the cost of other metrics, such as the retention of topology. Effects vary according to the input maps, with degree of variation in size of input regions found to be a factor. Optima exist for particular metrics in many cases, but at different amounts of whitespace for different maps. We suggest multiple metrics be used in optimized layouts, finding topology to be a primary factor in existing manually-crafted solutions, followed by a trade-off between shape and displacement. But the rich range of possible optimized layouts leads us to challenge single-solution thinking; we suggest to consider alternative optimized layouts for small multiples with gaps. Key to our work is the systematic, quantified and visual approach to exploring design spaces when facing a trade-off between many competing criteria-an approach likely to be of value to the analysis of other design spaces.
－ BibTeX
@article{small-multiples-with-gaps:2017,
title = {Small Multiples with Gaps},
author = {W. Meulemans and J. Dykes and A. Slingsby and C. Turkay and J. Wood},
year = {2017},
bookTitle = {IEEE Transactions on Visualization and Computer Graphics},
}
[ PDF ]
The Painter's Problem: Covering a Grid with Colored Connected Polygons
A.I. van Goethem, I. Kostitsyna, M. van Kreveld, W. Meulemans, M.F.M. Sondag, and J.J.H.M. Wulms.
arXiv,
2017.
－ Abstract
Motivated by a new way of visualizing hypergraphs, we study the following problem. Consider a rectangular grid and a set of colors χ. Each cell s in the grid is assigned a subset of colors χs⊆χ and should be partitioned such that for each color c∈χs at least one piece in the cell is identified with c. Cells assigned the empty color set remain white. We focus on the case where χ={red,blue}. Is it possible to partition each cell in the grid such that the unions of the resulting red and blue pieces form two connected polygons? We analyze the combinatorial properties and derive a necessary and sufficient condition for such a painting. We show that if a painting exists, there exists a painting with bounded complexity per cell. This painting has at most five colored pieces per cell if the grid contains white cells, and at most two colored pieces per cell if it does not.
－ BibTeX
@article{the-painter-s-problem-covering-a-grid-with-colored-connected-polygons:2017,
title = {The Painter's Problem: Covering a Grid with Colored Connected Polygons},
author = {A.I. van Goethem and I. Kostitsyna and M. van Kreveld and W. Meulemans and M.F.M. Sondag and J.J.H.M. Wulms},
year = {2017},
bookTitle = {arXiv},
}
[ PDF ]