Merge trees are a popular topological descriptor for scalar field data. A common measure to compare two merge trees is the interleaving distance, which relies on a mapping between the two merge trees, also referred to as an interleaving. Despite its desirable properties, the interleaving distance has not been used much in practice, largely due to the fact that computing the exact interleaving distance is NP-hard. In this paper, we show that the exact interleaving distance can be computed efficiently for merge trees encountered in practice: we present the first implementation of the exact fixed-parameter tractable (FPT) algorithm by Touli and Wang [Touli and Wang, 2022]. This algorithm uses a dynamic program to test if a specific interleaving distance δ is feasible. They bound the running time using a parameter τ that captures the number of mapping options between the two merge trees for the output distance δ. Our experiments show that, even though τ can become quite large for real-world merge trees, the running time of our implementation does not depend very heavily on τ. Furthermore, we modify the FPT algorithm into a sweepline algorithm that runs much faster in practice. Finally, we introduce a natural restriction for the interleaving distance capturing the geometric similarity between the underlying scalar fields. This restricted interleaving distance can be computed more efficiently and can, in some settings, also result in more meaningful interleavings. We extend our implementations to support these restrictions and demonstrate their effect on the running time of the algorithms.

Abstract The high‐level structure of a graph is a crucial ingredient for the analysis and visualization of relational data. However, discovering the salient graph patterns that form this structure is notoriously difficult for two reasons. (1) Finding important patterns, such as cliques and bicliques, is computationally hard. (2) Real‐world graphs contain noise, and therefore do not always exhibit patterns in their pure form. Defining meaningful noisy patterns and detecting them efficiently is a currently unsolved challenge. In this paper, we propose to use well‐ordered matrices as a tool to both define and effectively detect noisy patterns. Specifically, we represent a graph as its adjacency matrix and optimally order it using Moran's I. Standard graph patterns (cliques, bicliques, and stars) now translate to rectangular submatrices. Using Moran's I, we define a permitted level of noise for such patterns. A combination of exact algorithms and heuristics allows us to efficiently decompose the matrix into noisy patterns. We also introduce a novel motif simplification that visualizes noisy patterns while explicitly encoding the level of noise. We showcase our techniques on several real‐world data sets.

Merge trees are a powerful tool from topological data analysis that is frequently used to analyze scalar fields. The similarity between two merge trees can be captured by an interleaving: a pair of maps between the trees that jointly preserve ancestor relations in the trees. Interleavings can have a complex structure; visualizing them requires a sense of (drawing) order which is not inherent in this purely topological concept. However, in practice it is often desirable to introduce additional geometric constraints, which leads to variants such as labeled or monotone interleavings. Monotone interleavings respect a given order on the leaves of the merge trees and hence have the potential to be visualized in a clear and comprehensive manner.In this paper, we introduce ParkView: a schematic, scalable encoding for monotone interleavings. ParkView captures both maps of the interleaving using an optimal decomposition of both trees into paths and corresponding branches. We prove several structural properties of monotone interleavings, which support a sparse visual encoding using active paths and hedges that can be linked using a maximum of 6 colors for merge trees of arbitrary size. We show how to compute an optimal path-branch decomposition in linear time and illustrate ParkView on a number of real-world datasets.

Merge trees are a common topological descriptor for data with a hierarchical component, such as terrains and scalar fields. The interleaving distance, in turn, is a common distance for comparing merge trees. However, the interleaving distance for merge trees is solely based on the hierarchical structure, and disregards any other geometrical or topological properties that might be present in the underlying data. Furthermore, the interleaving distance is NP-hard to compute.

Let P be a polygon with k vertices. Let R and B be two simple, interior disjoint curves on the boundary of P, with n and m vertices. We show how to compute the Fréchet distance between R and B using the geodesic L₁-distance in P in (k log nm + (n+m) (log² nm log k + log⁴ nm)) time.

Abstract Polycube segmentations for 3D models effectively support a wide variety of applications such as seamless texture mapping, spline fitting, structured multi‐block grid generation, and hexahedral mesh construction. However, the automated construction of valid polycube segmentations suffers from robustness issues: state‐of‐the‐art methods are not guaranteed to find a valid solution. In this paper we present DualCube: an iterative algorithm which is guaranteed to return a valid polycube segmentation for 3D models of any genus. Our algorithm is based on a dual representation of polycubes. Starting from an initial simple polycube of the correct genus, together with the corresponding dual loop structure and polycube segmentation, we iteratively refine the polycube, loop structure, and segmentation, while maintaining the correctness of the solution. DualCube is robust by construction: at any point during the iterative process the current segmentation is valid. Its iterative nature furthermore facilitates a seamless trade‐off between quality and complexity of the solution. DualCube can be implemented using comparatively simple algorithmic building blocks; our experimental evaluation establishes that the quality of our polycube segmentations is on par with, or exceeding, the state‐of‐the‐art.

Points of interest on a map such as restaurants, hotels, or subway stations, give rise to categorical point data: data that have a fixed location and one or more categorical attributes. Consequently, recent years have seen various set visualization approaches that visually connect points of the same category to support users in understanding the spatial distribution of categories. Existing methods use complex and often highly irregular shapes to connect points of the same category, leading to high cognitive load for the user. In this paper we introduce SimpleSets, which uses simple shapes to enclose categorical point patterns, thereby providing a clean overview of the data distribution. SimpleSets is designed to visualize sets of points with a single categorical attribute; as a result, the point patterns enclosed by SimpleSets form a partition of the data. We give formal definitions of point patterns that correspond to simple shapes and describe an algorithm that partitions categorical points into few such patterns. Our second contribution is a rendering algorithm that transforms a given partition into a clean set of shapes resulting in an aesthetically pleasing set visualization. Our algorithm pays particular attention to resolving intersections between nearby shapes in a consistent manner. We compare SimpleSets to the state-of-the-art set visualizations using standard datasets from the literature.

The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. The best algorithm currently known for the reconfiguration problem, by Abel and Kominers [arXiv, 2011], uses O(n3) moves to transform any n-cube configuration into any other n-cube configuration. As is common in the literature, this algorithm reconfigures the input into an intermediate canonical shape. In this paper we present an in-place algorithm that reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. This result is asymptotically optimal. Furthermore, our algorithm directly extends to dimensions higher than three.

Isolines visually characterize scalar fields by connecting all points of the same value by a closed curve at repeated intervals. They work only as a set which gives the viewer an indication of the shape of the underlying field. Hence, when simplifying isolines it is important that the correspondence - the harmony - between adjacent isolines is preserved whenever it is present. The majority of state-of-the-art simplification methods treat isolines independently; at best they avoid collisions between adjacent simplified isolines. A notable exception is the work by Van Goethem et al. (2021) who were the first to introduce the concept of harmony between adjacent isolines explicitly as an algorithmic design principle. They presented a proof-of-concept algorithm that harmoniously simplifies a sequence of polylines. However, the sets of isolines of scalar fields, most notably terrain, consist of closed curves which are nested in arbitrarily complex ways and not of an ordered sequence of polylines. In this paper we significantly extend the work by Van Goethem et al. (2021) to capture harmony in general sets of isolines. Our new simplification algorithm can handle sets of isolines describing arbitrary scalar fields and is more efficient, allowing us to harmoniously simplify terrain with hundreds of thousands of vertices. We experimentally compare our method to the results of Van Goethem et al. (2021) on bundles of isolines and to general simplification methods on isolines extracted from DEMs of Antartica. Our results indicate that our method efficiently preserves the harmony in the simplified maps, which are thereby less noisy, cartographically more meaningful, and easier to read.

Given two sets $R$ and $B$ of $n$ points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the "red" points in $R$ from the "blue" points in $B$ and is robust to outliers. More precisely, we find a region $\mathcal{W}_B$ bounded by two lines, so either a halfplane, strip, wedge, or double wedge, containing (most of) the blue points $B$, and few red points. Our running times vary between optimal $O(n\log n)$ and around $O(n^3)$, depending on the type of region $\mathcal{W}_B$ and whether we wish to minimize only red outliers, only blue outliers, or both.

Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group's shape carries meaning as well. In this paper, we represent a group's shape using a simple geometric object, a line segment. Specifically, given a radius $r$, we say a line segment is representative of a point set $P$ if it is within distance $r$ of each point $p \in P$. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius $r$ using the shortest line segment. We describe an algorithm to find the shortest representative segment in $O(n \log h + h \log^3 h)$ time. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in $P$ move.

Visualizing a graph directly via its adjacency matrix is a common and effective technique. Such matrix visualizations rely crucially on a good ordering of the vertices to highlight intrinsic patterns in the graph. When analyzing collections of graphs, such as time varying sequences or connectivity information ranging over multiple specimens, the user currently needs to make the choice: either order each graph individually to optimize its ordering quality, or use a single, simultaneous ordering for all graphs in the collection, which necessarily reduces the ordering quality for the individual graphs.In this paper we explore the space of contextual orderings that lie between these two extremes. Intuitively, contextual orderings maintain a higher level of consistency than individual orderings and deliver a higher ordering quality than simultaneous orderings. To formally reason about contextual orderings we define a distance measure between orderings which is based on individual block moves (IBM). The IBM distance allows us to relate consistency within the context of the collection with ordering quality. Specifically, we define the consistency of an ordering as the IBM distance to the simultaneous ordering for the collection. Our experiments show that already at a small IBM distance to the simultaneous ordering we can find contextual orderings with significantly improved ordering quality. Furthermore, we can create orderings that are nearly as good as individual orderings, but exhibit considerably improved consistency. We hence believe that contextual orderings can enable a more fine-grained analysis of graph collections, by allowing the user to focus on individual graphs while maintaining a sense of the context they appear in.

The Fréchet distance is a commonly used similarity measure between curves. It is known how to compute the continuous Fréchet distance between two polylines with m and n vertices in ℝd in O(mn(log log n)2) time; doing so in strongly subquadratic time is a longstanding open problem. Recent conditional lower bounds suggest that it is unlikely that a strongly subquadratic algorithm exists. Moreover, it is unlikely that we can approximate the Fréchet distance to within a factor 3 in strongly subquadratic time, even if d = 1. The best current results establish a tradeoff between approximation quality and running time. Specifically, Colombe and Fox (SoCG, 2021) give an O(α)-approximate algorithm that runs in O((n3/α2) log n) time for any , assuming m ≤ n. In this paper, we improve this result with an O(α)-approximate algorithm that runs in O((n + mn/α) log3 n) time for any α ∈ [1, n], assuming m ≤ n and constant dimension d. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.12721

Bias elimination and recent probing studies attempt to remove specific information from embedding spaces.Here it is important to remove as much of the target information as possible, while preserving any other information present.INLP is a popular recent method which removes specific information through iterative nullspace projections.Multiple iterations, however, increase the risk that information other than the target is negatively affected.We introduce two methods that find a single targeted projection: Mean Projection (MP, more efficient) and Tukey Median Projection (TMP, with theoretical guarantees).Our comparison between MP and INLP shows that (1) one MP projection removes linear separability based on the target and (2) MP has less impact on the overall space.Further analysis shows that applying random projections after MP leads to the same overall effects on the embedding space as the multiple projections of INLP.Applying one targeted (MP) projection hence is methodologically cleaner than applying multiple (INLP) projections that introduce random effects.

An important data source for traffic analysis is GPS trajectory data. However, due to measurement inaccuracies, such data does not necessarily align well with data describing the road network. Hence, GPS data typically needs to be aligned with the road network before further analysis can take place; this process is called map matching. The challenges in map matching are exacerbated when trajectories are sparse (have a low measurement frequency); we then need to fill the gaps between the measurements with a realistic estimate of the actual route between two points. As vehicle movement is subject to physical constraints (such as acceleration and speed bounds), an estimated route should be physically consistent. We present a method that creates physically consistent estimated routes to perform map matching for sparse trajectories.

Topological Data Analysis (TDA) focuses on the inherent shape of (spatial) data. As such, it may provide useful methods to explore spatial representations of linguistic data (embeddings) which have become central in NLP. In this paper we aim to introduce TDA to researchers in language technology. We use TDA to represent document structure as so-called story trees. Story trees are hierarchical representations created from semantic vector representations of sentences via persistent homology. They can be used to identify and clearly visualize prominent components of a story line. We showcase their potential by using story trees to create extractive summaries for news stories.

The preprocessing model for uncertain data models geometric imprecision of algorithmic input and provides a framework for working with it. In this model, we are given a set of regions ℛ which model the uncertainty associated with an unknown set of points P. There are two phases: a preprocessing phase, in which we have access only to ℛ, followed by a reconstruction phase, in which we have access to points in P, possibly at a certain retrieval cost C per point. For a given algorithmic problem, the goal in this model is to perform as much of the necessary computations as possible in the preprocessing phase, so that the amount of time spent in the reconstruction phase is minimized. In this paper, we investigate the following algorithmic question: how fast can we compute the Pareto front of P in the preprocessing model? We show that if ℛ is a set of pairwise-disjoint axis-aligned rectangles then we can preprocess ℛ to reconstruct the Pareto front of P efficiently. In contrast to earlier work in the preprocessing model, our solution achieves sublinear reconstruction time when the output complexity is sublinear. To refine our algorithmic analysis, we introduce a new notion of algorithmic optimality which relates to the entropy of the uncertainty regions. Our proposed uncertainty-region optimality falls on the spectrum between worst-case optimality and instance optimality. Our results are worst-case optimal, but we prove that instance optimality is unobtainable for a wide class of problems in the preprocessing model. We prove that, in fact, our results are uncertainty-region optimal with respect to real RAM instructions in the reconstruction phase.

The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material. Even though the particles are restricted to local communication, local movement, and simple computation, their actions can nevertheless result in the global change of the material's physical properties and geometry. A fundamental algorithmic task for programmable matter is to achieve global shape reconfiguration by specifying local behavior of the particles. In this paper we describe a new approach for shape reconfiguration in the \emph{amoebot} model. The amoebot model is a distributed model which significantly restricts memory, computing, and communication capacity of the individual particles. Thus the challenge lies in coordinating the actions of particles to produce the desired behavior of the global system. Our reconfiguration algorithm is the first algorithm that does not use a canonical intermediate configuration when transforming between arbitrary shapes. We introduce new geometric primitives for amoebots and show how to reconfigure particle systems, using these primitives, in a linear number of activation rounds in the worst case. In practice, our method exploits the geometry of the symmetric difference between input and output shape: it minimizes unnecessary disassembly and reassembly of the particle system when the symmetric difference between the initial and the target shapes is small. Furthermore, our reconfiguration algorithm moves the particles over as many parallel shortest paths as the problem instance allows.

Abstract We study an agglomerative clustering problem motivated by interactive glyphs in geo-visualization. Consider a set of disjoint square glyphs on an interactive map. When the user zooms out, the glyphs grow in size relative to the map, possibly with different speeds. When two glyphs intersect, we wish to replace them by a new glyph that captures the information of the intersecting glyphs. We present a fully dynamic kinetic data structure that maintains a set of n disjoint growing squares. Our data structure uses $$O\bigl (n \log n \log \log n\bigr )$$ O ( n log n log log n ) space, supports queries in worst case $$O\bigl (\log ^2 n\bigr )$$ O ( log 2 n ) time, and updates in $$O\bigl (\log ^5 n\bigr )$$ O ( log 5 n ) amortized time. This leads to an $$O\bigl (n\,\alpha (n)\log ^5 n\bigr )$$ O ( n α ( n ) log 5 n ) time algorithm to solve the agglomerative clustering problem. This is a significant improvement over the current best $$O\bigl (n^2\bigr )$$ O ( n 2 ) time algorithms.

Undirected graphs are frequently used to model phenomena that deal with interacting objects, such as social networks, brain activity and communication networks. The topology of an undirected graph G can be captured by an adjacency matrix; this matrix in turn can be visualized directly to give insight into the graph structure. Which visual patterns appear in such a matrix visualization crucially depends on the ordering of its rows and columns. Formally defining the quality of an ordering and then automatically computing a high-quality ordering are both challenging problems; however, effective heuristics exist and are used in practice. Often, graphs do not exist in isolation but as part of a collection of graphs on the same set of vertices, for example, brain scans over time or of different people. To visualize such graph collections, we need a single ordering that works well for all matrices simultaneously. The current state-of-the-art solves this problem by taking a (weighted) union over all graphs and applying existing heuristics. However, this union leads to a loss of information, specifically in those parts of the graphs which are different. We propose a collection-aware approach to avoid this loss of information and apply it to two popular heuristic methods: leaf order and barycenter.The de-facto standard computational quality metrics for matrix ordering capture only block-diagonal patterns (cliques). Instead, we propose to use Moran's I, a spatial auto-correlation metric, which captures the full range of established patterns. Moran's I refines previously proposed stress measures. Furthermore, the popular leaf order method heuristically optimizes a similar measure which further supports the use of Moran's I in this context. An ordering that maximizes Moran's I can be computed via solutions to the Traveling Salesperson Problem (TSP); orderings that approximate the optimal ordering can be computed more efficiently, using any of the approximation algorithms for metric TSP. We evaluated our methods for simultaneous orderings on real-world datasets using Moran's I as the quality metric. Our results show that our collection-aware approach matches or improves performance compared to the union approach, depending on the similarity of the graphs in the collection. Specifically, our Moran's I-based collection-aware leaf order implementation consistently outperforms other implementations. Our collection-aware implementations carry no significant additional computational costs.

The availability of devices that track moving objects has led to an explosive growth in trajectory data. When exploring the resulting large trajectory collections, visual summaries are a useful tool to identify time intervals of interest. A typical approach is to represent the spatial positions of the tracked objects at each time step via a one-dimensional ordering; visualizations of such orderings can then be placed in temporal order along a time line. There are two main criteria to assess the quality of the resulting visual summary: spatial quality - how well does the ordering capture the structure of the data at each time step, and stability - how coherent are the orderings over consecutive time steps or temporal ranges?In this paper we introduce a new Stable Principal Component (SPC) method to compute such orderings, which is explicitly parameterized for stability, allowing a trade-off between the spatial quality and stability. We conduct extensive computational experiments that quantitatively compare the orderings produced by ours and other stable dimensionality-reduction methods to various state-of-the-art approaches using a set of well-established quality metrics that capture spatial quality and stability. We conclude that stable dimensionality reduction outperforms existing methods on stability, without sacrificing spatial quality or efficiency; in particular, our new SPC method does so at a fraction of the computational costs.

We study a fundamental question from graph drawing: given a pair $(G,C)$ of a graph $G$ and a cycle $C$ in $G$ together with a simple polygon $P$, is there a straight-line drawing of $G$ inside $P$ which maps $C$ to $P$? We say that such a drawing of $(G,C)$ respects $P$. We fully characterize those instances $(G,C)$ which are polygon-universal, that is, they have a drawing that respects $P$ for any simple (not necessarily convex) polygon $P$. Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance $(G,C)$ is planar, that is, if there exists a planar drawing of $G$ with $C$ on the outer face, we show that the same conditions guarantee for every simple polygon $P$ the existence of a planar drawing of $(G,C)$ that respects $P$. If $(G,C)$ is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon $P$.

Understanding human mobility patterns is an important aspect of traffic analysis and urban planning. Trajectory data provide detailed views on specific routes, but typically do not capture all traffic. On the other hand, loop detectors built into the road network capture all traffic flow at specific locations, but provide no information on the individual routes. Given a set of loop-detector measurements as well as a (small) set of representative trajectories, our goal is to investigate how one can effectively combine these two partial data sources to create a more complete picture of the underlying mobility patterns. Specifically, we want to reconstruct a realistic set of routes from the loop-detector data, using the given trajectories as representatives of typical behavior.

Machine learning and data mining techniques are effective tools to classify large amounts of data. But they tend to preserve any inherent bias in the data, for example, with regards to gender or race. Removing such bias from data or the learned representations is quite challenging. In this paper we study a geometric problem which models a possible approach for bias removal. Our input is a set of points P in Euclidean space Rd and each point is labeled with k binary-valued properties. A priori we assume that it is "easy"to classify the data according to each property. Our goal is to obstruct the classification according to one property by a suitable projection to a lower-dimensional Euclidean space Rm (m < d), while classification according to all other properties remains easy. What it means for classification to be easy depends on the classification model used. We first consider classification by linear separability as employed by support vector machines. We use Kirchberger's Theorem to show that, under certain conditions, a simple projection to Rd1 suffices to eliminate the linear separability of one of the properties whilst maintaining the linear separability of the other properties. We also study the problem of maximizing the linear "inseparability"of the chosen property. Second, we consider more complex forms of separability and prove a connection between the number of projections required to obstruct classification and the Helly-type properties of such separabilities.

Grid maps are spatial arrangements of simple tiles (often squares or hexagons), each of which represents a spatial element. They are an established, effective way to show complex data per spatial element, using visual encodings within each tile ranging from simple coloring to nested small-multiples visualizations. An effective grid map is coherent with the underlying geographic space: the tiles maintain the contiguity, neighborhoods and identifiability of the corresponding spatial elements, while the grid map as a whole maintains the global shape of the input. Of particular importance are salient local features of the global shape which need to be represented by tiles assigned to the appropriate spatial elements. State-of-the-art techniques can adequately deal only with simple cases, such as close-to-uniform spatial distributions or global shapes that have few characteristic features. We introduce a simple fully-automated 3-step pipeline for computing coherent grid maps. Each step is a well-studied problem: shape decomposition based on salient features, tile-based Mosaic Cartograms, and point-set matching. Our pipeline is a seamless composition of existing techniques for these problems and results in high-quality grid maps. We provide an implementation, demonstrate the efficacy of our approach on various complex datasets, and compare it to the state-of-the-art.

Rectangular treemaps visualize hierarchical numerical data by recursively partitioning an input rectangle into smaller rectangles whose areas match the data. Numerical data often has uncertainty associated with it. To visualize uncertainty in a rectangular treemap, we identify two conflicting key requirements: (i) to assess the data value of a node in the hierarchy, the area of its rectangle should directly match its data value, and (ii) to facilitate comparison between data and uncertainty, uncertainty should be encoded using the same visual variable as the data, that is, area. We present Uncertainty Treemaps, which meet both requirements simultaneously by introducing the concept of hierarchical uncertainty masks. First, we define a new cost function that measures the quality of Uncertainty Treemaps. Then, we show how to adapt existing treemapping algorithms to support uncertainty masks. Finally, we demonstrate the usefulness and quality of our technique through an expert review and a computational experiment on real-world datasets.

Face-connected configurations of cubes are a common model for modular robots in three dimensions. In this abstract and the accompanying video we study reconfigurations of such modular robots using so-called sliding moves. Using sliding moves, it is always possible to reconfigure one face-connected configuration of n cubes into any other, while keeping the robot connected at all stages of the reconfiguration. For certain configurations Ω(n²) sliding moves are necessary. In contrast, the best current upper bound is O(n³). It has been conjectured that there is always a cube on the outside of any face-connected configuration of cubes which can be moved without breaking connectivity. The existence of such a cube would immediately imply a straight-forward O(n²) reconfiguration algorithm. However, we present a configuration of cubes such that no cube on the outside can move without breaking connectivity. In other words, we show that this particular avenue towards an O(n²) reconfiguration algorithm for face-connected cubes is blocked.

Abstract Rectangular treemaps are often the method of choice to visualize large hierarchical datasets. Nowadays such datasets are available over time, hence there is a need for (a) treemaps that can handle time‐dependent data, and (b) corresponding quality criteria that cover both a treemap's visual quality and its stability over time. In recent years a wide variety of (stable) treemapping algorithms has been proposed, with various advantages and limitations. We aim to provide insights to researchers and practitioners to allow them to make an informed choice when selecting a treemapping algorithm for specific applications and data. To this end, we perform an extensive quantitative evaluation of rectangular treemaps for time‐dependent data. As part of this evaluation we propose a novel classification scheme for time‐dependent datasets. Specifically, we observe that the performance of treemapping algorithms depends on the characteristics of the datasets used. We identify four potential representative features that characterize time‐dependent hierarchical datasets and classify all datasets used in our experiments accordingly. We experimentally test the validity of this classification on more than 2000 datasets, and analyze the relative performance of 14 state‐of‐the‐art rectangular treemapping algorithms across varying features. Finally, we visually summarize our results with respect to both visual quality and stability to aid users in making an informed choice among treemapping algorithms. All datasets, metrics, and algorithms are openly available to facilitate reuse and further comparative studies.

We study an agglomerative clustering problem motivated by visualizing disjoint glyphs (represented by geometric shapes) centered at specific locations on a geographic map. As we zoom out, the glyphs grow and start to overlap. We replace overlapping glyphs by one larger merged glyph to maintain disjointness. Our goal is to compute the resulting hierarchical clustering efficiently in practice. A straightforward algorithm for such spatial agglomerative clustering runs in O(n2 log n) time, where n is the number of glyphs. This is not efficient enough for many real-world datasets which contain up to tens or hundreds of thousands of glyphs. Recently the theoretical upper bound was improved to O(nα(n) log7 n) time [10], where α(n) is the extremely slow growing inverse Ackermann function. Although this new algorithm is asymptotically much faster than the naive algorithm, from a practical point of view, it does not perform better for n ≤ 106. In this paper we present a new agglomerative clustering algorithm which works efficiently in practice. Our algorithm relies on the use of quadtrees to speed up spatial computations. Interestingly, even in non-pathological datasets we can encounter large glyphs that intersect many quadtree cells and that are involved in many clustering events. We therefore devise a special strategy to handle such large glyphs. We test our algorithm on several synthetic and real-world datasets and show that it performs well in practice.

Let ${R} = \{R_1, R_2, ..., R_n\}$ be a set of regions and let $ X = \{x_1, x_2, ..., x_n\}$ be an (unknown) point set with $x_i \in R_i$. Region $R_i$ represents the uncertainty region of $x_i$. We consider the following question: how fast can we establish order if we are allowed to preprocess the regions in $R$? The preprocessing model of uncertainty uses two consecutive phases: a preprocessing phase which has access only to ${R}$ followed by a reconstruction phase during which a desired structure on $X$ is computed. Recent results in this model parametrize the reconstruction time by the ply of ${R}$, which is the maximum overlap between the regions in ${R}$. We introduce the ambiguity $A({R})$ as a more fine-grained measure of the degree of overlap in ${R}$. We show how to preprocess a set of $d$-dimensional disks in $O(n \log n)$ time such that we can sort $X$ (if $d=1$) and reconstruct a quadtree on $X$ (if $d\geq 1$ but constant) in $O(A({R}))$ time. If $A({R})$ is sub-linear, then reporting the result dominates the running time of the reconstruction phase. However, we can still return a suitable data structure representing the result in $O(A({R}))$ time. In one dimension, ${R}$ is a set of intervals and the ambiguity is linked to interval entropy, which in turn relates to the well-studied problem of sorting under partial information. The number of comparisons necessary to find the linear order underlying a poset $P$ is lower-bounded by the graph entropy of $P$. We show that if $P$ is an interval order, then the ambiguity provides a constant-factor approximation of the graph entropy. This gives a lower bound of $Ω(A({R}))$ in all dimensions for the reconstruction phase (sorting or any proximity structure), independent of any preprocessing; hence our result is tight.

Trajectories are usually collected with physical sensors, which are prone to errors and cause outliers in the data. We aim to identify such outliers via the physical properties of the tracked entity, that is, we consider its physical possibility to visit combinations of measurements. We describe optimal algorithms to compute maximum subsequences of measurements that are consistent with (simplified) physics models. Our results are output-sensitive with respect to the number k of outliers in a trajectory of n measurements. Specifically, we describe an O(n log n log2 k) time algorithm for 2D trajectories using a model with unbounded acceleration but bounded velocity, and an O(nk) time algorithm for any model where consistency is "concatenable": a consistent subsequence that ends where another begins together form a consistent sequence. We also consider acceleration-bounded models which are not concatenable. We show how to compute the maximum subsequence for such models in O(nk2 log k) time, under appropriate realism conditions. Finally, we experimentally explore the performance of our algorithms on several large real-world sets of trajectories. Our experiments show that we are generally able to retain larger fractions of noisy trajectories than previous work and simpler greedy approaches. We also observe that the speed-bounded model may in practice approximate the acceleration-bounded model quite well, though we observed some variation between datasets.

We show by reduction from the Orthogonal Vectors problem that algorithms with strongly subquadratic running time cannot approximate the Fréchet distance between curves better than a factor 3 unless SETH fails. We show that similar reductions cannot achieve a lower bound with a factor better than 3. Our lower bound holds for the continuous, the discrete, and the weak discrete Fréchet distance even for curves in one dimension. Interestingly, the continuous weak Fréchet distance behaves differently. Our lower bound still holds for curves in two dimensions and higher. However, for curves in one dimension, we provide an exact algorithm to compute the weak Fréchet distance in linear time.

We propose a novel type of low distortion radial embedding which focuses on one specific entity and its closest neighbors. Our embedding preserves near-exact distances to the focus entity and aims to minimize distortion between the other entities. We present an interactive exploration tool SolarView which places the focus entity at the center of a "solar system" and embeds its neighbors guided by concentric circles. SolarView provides an implementation of our novel embedding and several state-of-the-art dimensionality reduction and embedding techniques, which we adapted to our setting in various ways. We experimentally evaluated our embedding and compared it to these state-of-the-art techniques. The results show that our embedding competes with these techniques and achieves low distortion in practice. Our method performs particularly well when the visualization, and hence the embedding, adheres to the solar system design principle of our application. Nonetheless-as with all dimensionality reduction techniques-the distortion may be high. We leverage interaction techniques to give clear visual cues that allow users to accurately judge distortion. We illustrate the use of SolarView by exploring the high-dimensional metric space of bibliographic entity similarities.

Linear layouts are a simple and natural way to draw a graph: all vertices are placed on a single line and edges are drawn as arcs between the vertices. Despite its simplicity, a linear layout can be a very meaningful visualization if there is a particular order defined on the vertices. Common examples of such ordered - and often also directed - graphs are event sequences and processes. A main drawback of linear layouts are the usually (very) large aspect ratios of the resulting drawings, which prevent users from obtaining a good overview of the whole graph. In this paper we present a novel and versatile algorithm to optimally fold a linear layout of a graph such that it can be drawn nicely in a specified aspect ratio, while still clearly communicating the linearity of the layout. Our algorithm allows vertices to be drawn as blocks or rectangles of specified sizes to incorporate different drawing styles, label sizes, and even recursive structures. For reasonably-sized drawings the folded layout can be computed interactively. We demonstrate the applicability of our algorithm on graphs that represent process trees, a particular type of process model. Our algorithm arguably produces much more readable layouts than existing methods.

This abstract describes how tools from network analysis and visualization can successfully support the study of philosophical questions in social epistemology. We introduce a particular network structure, namely the (m, k)-observer. We argue for its epistemic value and show that such observers are extremely rare in social media discussions of controversial topics. Our specific use case concerns a discussion of vaccine safety on Twitter.

Linear features on terrains model the boundaries of ground cover regions, delineate glaciers, or form the boundary of rivers and lakes. When computing the similarity between such linear features, it is important to also take their context into account: the terrain. We hence explore the possibilities of volume-based distance measures for linear features on a terrain. Our measures construct suitable base surfaces between the linear features, which can slice through the input terrain and also hover above. The similarity between two linear features is then captured by the volume of "earth" above the base surface and below the terrain, and possibly also by the volume of "air" below the base surface and above the terrain. We suggest six ways of choosing a suitable base surface. These choices give rise to different measured volumes and can be useful in different application scenarios.

Treemaps are a popular tool to visualize hierarchical data: items are represented by nested rectangles and the area of each rectangle corresponds to the data being visualized for this item. The visual quality of a treemap is commonly measured via the aspect ratio of the rectangles. If the data changes, then a second important quality criterion is the stability of the treemap: how much does the treemap change as the data changes. We present a novel stable treemapping algorithm that has very high visual quality. Whereas existing treemapping algorithms generally recompute the treemap every time the input changes, our algorithm changes the layout of the treemap using only local modifications. This approach not only gives us direct control over stability, but it also allows us to use a larger set of possible layouts, thus provably resulting in treemaps of higher visual quality compared to existing algorithms. We further prove that we can reach all possible treemap layouts using only our local modifications. Furthermore, we introduce a new measure for stability that better captures the relative positions of rectangles. We finally show via experiments on real-world data that our algorithm outperforms existing treemapping algorithms also in practice on either visual quality and/or stability. Our algorithm scores high on stability regardless of whether we use an existing stability measure or our new measure.

Drainage networks on terrains have been studied extensively from an algorithmic perspective. However, in drainage networks water flow cannot bifurcate and hence they do not model braided rivers (multiple channels which split and join, separated by sediment bars). We initiate the algorithmic study of braided rivers by employing the descending quasi Morse-Smale complex on the river bed (a polyhedral terrain), and extending it with a certain ordering of bars from the one river bank to the other. This allows us to compute a graph that models a representative channel network, consisting of lowest paths. To ensure that channels in this network are sufficiently different we define a sand function that represents the volume of sediment separating them. We show that in general the problem of computing a maximum network of non-crossing channels which are delta-different from each other (as measured by the sand function) is NP-hard. However, using our ordering between the river banks, we can compute a maximum delta-different network that respects this order in polynomial time. We implemented our approach and applied it to simulated and real-world braided rivers.

Computing optimal deformations between two curves is a fundamental question with various applications, and has recently received much attention in both computational topology and in mathematics in the form of homotopies of disks and annular regions. In this paper, we examine this problem in a geometric setting, where we consider the boundary of a polygonal domain with spikes, point obstacles that can be crossed at an additive cost. We aim to continuously morph from one part of the boundary to another, necessarily passing over all spikes, such that the most expensive intermediate curve is minimized, where the cost of a curve is its geometric length plus the cost of any spikes it crosses. We first investigate the general setting where each spike may have a different cost. For the number of inflection points in an intermediate curve, we present a lower bound that is linear in the number of spikes, even if the domain is convex and the two boundaries for which we seek a morph share an endpoint. We describe a 2-approximation algorithm for the general case, and an optimal algorithm for the case that the two boundaries for which we seek a morph share both endpoints, thereby representing the entire boundary of the domain. We then consider the setting where all spikes have the same unit cost and we describe a polynomial-time exact algorithm. The algorithm combines structural properties of homotopies arising from the geometry with methodology for computing Fréchet distances.

Motivated by the question of simultaneous embedding of several flow maps, we consider the problem of drawing multiple geometric Steiner arborescences with no crossings in the rectilinear and in the angle-restricted setting. When terminal-to-root paths are allowed to turn freely, we show that two rectilinear Steiner arborescences have a non-crossing drawing if neither tree necessarily completely disconnects the other tree and if the roots of both trees are "free". If the roots are not free, then we can reduce the decision problem to 2SAT. If terminal-to-root paths are allowed to turn only at Steiner points, then it is NP-hard to decide whether multiple rectilinear Steiner arborescences have a non-crossing drawing. The setting of angle-restricted Steiner arborescences is more subtle than the rectilinear case. Our NP-hardness result extends, but testing whether there exists a non-crossing drawing if the roots of both trees are free requires additional conditions to be fulfilled.

The Fréchet distance is a well-studied measure for the similarity of shapes. While efficient algorithms for computing the Fréchet distance between curves exist, there are only few results on the Fréchet distance between surfaces. Recent work has shown that the Fréchet distance is computable between piecewise linear functions f and g: M → ℝk with M a triangulated surface of genus zero. We focus on the case k =1 and M being a topological sphere or disk with constant boundary. Intuitively, we measure the distance between terrains based solely on the height function. Our main result is that in this case computing the Frechet distance between f and g is in NP. We additionally show that already for k = 1, computing a factor 2 – ∊ approximation of the Fréchet distance is NP-hard, showing that this problem is in fact NP-complete. We also define an intermediate distance, between contour trees, which we also show to be NP- complete to compute. Finally, we discuss how our and other distance measures between contour trees relate to each other.

Time series (such as stock prices) and ensembles (such as model runs for weather forecasts) are two important types of one-dimensional time-varying data. Such data is readily available in large quantities but visual analysis of the raw data quickly becomes infeasible, even for moderately sized data sets. Trend detection is an effective way to simplify time-varying data and to summarize salient information for visual display and interactive analysis. We propose a geometric model for trend-detection in one-dimensional time-varying data, inspired by topological grouping structures for moving objects in two- or higher-dimensional space. Our model gives provable guarantees on the trends detected and uses three natural parameters: granularity, support-size, and duration. These parameters can be changed on-demand. Our system also supports a variety of selection brushes and a time-sweep to facilitate refined searches and interactive visualization of (sub-)trends. We explore different visual styles and interactions through which trends, their persistence, and evolution can be explored.

Word clouds are a popular method to visualize the frequency of words in textual data. Nowadays many text-based data sets, such as Flickr tags, are geo-referenced, that is, they have an important spatial component. However, existing automated methods to generate word clouds are unable to incorporate such spatial information. We introduce geo word clouds: word clouds which capture not only the frequency but also the spatial relevance of words. Our input is a set of locations from one (or more) geographic regions with (possibly several) text labels per location. We aggregate word frequencies according to point clusters and employ a greedy strategy to place appropriately sized labels without overlap as close as possible to their corresponding locations. While doing so we "draw" the spatial shapes of the geographic regions with the corresponding labels. We experimentally explore trade-offs concerning the location of labels, their relative sizes and the number of spatial clusters. The resulting word clouds are visually pleasing and have a low error in terms of relative scaling and locational accuracy of words, while using a small number of clusters per label.

Upper and lower bounds for the number of geometric graphs of specific types on a given set of points in the plane have been intensively studied in recent years. For most classes of geometric graphs it is now known that point sets in convex position minimize their number. However, it is still unclear which point sets minimize the number of geometric triangulations; the so-called double circles are conjectured to be the minimizing sets. In this paper we prove that any set of n points in general position in the plane has at least Omega(2.631^n) geometric triangulations. Our result improves the previously best general lower bound of Omega(2.43^n) and also covers the previously best lower bound of Omega(2.63^n) for a fixed number of extreme points. We achieve our bound by showing and combining several new results, which are of independent interest: (1) Adding a point on the second convex layer of a given point set (of 7 or more points) at least doubles the number of triangulations. (2) Generalized configurations of points that minimize the number of triangulations have at most n/2 points on their convex hull. (3) We provide tight lower bounds for the number of triangulations of point sets with up to 15 points. These bounds further support the double circle conjecture.

We present algorithms and data structures that support the interactive analysis of the grouping structure of one-, two-, or higher-dimensional time-varying data while varying all defining parameters. Grouping structures characterise important patterns in the temporal evaluation of sets of time-varying data. We follow Buchin et al. [JoCG 2015] who define groups using three parameters: group-size, group-duration, and inter-entity distance. We give upper and lower bounds on the number of maximal groups over all parameter values, and show how to compute them efficiently. Furthermore, we describe data structures that can report changes in the set of maximal groups in an output-sensitive manner. Our results hold in R^d for fixed d.

We present an efficient technique for topology-preserving map deformation and apply it to the visualization of dissimilarity data in a geographic context. Map deformation techniques such as value-by-area cartograms are well studied. However, using deformation to highlight (dis)similarity between locations on a map in terms of their underlying data attributes is novel. We also identify an alternative way to represent dissimilarities on a map through the use of visual overlays. These overlays are complementary to deformation techniques and enable us to assess the quality of the deformation as well as to explore the design space of blending the two methods. Finally, we demonstrate how these techniques can be useful in several-quite different-applied contexts: travel-time visualization, social demographics research and understanding energy flowing in a wide-area power-grid.

The classic method to depict graphs is a node-link diagram where vertices (nodes) are associated with each object and edges (links) connect related objects. However, node-link diagrams quickly appear cluttered and unclear, even for moderately sized graphs. If the positions of the nodes are fixed then suitable link routing is the only option to reduce clutter. We present a novel link clustering and routing algorithm which respects (and if desired refines) user-defined clusters on links. If no clusters are defined a priori we cluster based on geometric criteria, that is, based on a well-separated pair decomposition (WSPD).We route link clusters individually on a sparse visibility spanner. To completely avoid ambiguity we draw each individual link and ensure that clustered links follow the same path in the routing graph. We prove that the clusters induced by the WSPD consist of compatible links according to common similarity measures as formalized by Holten and van Wijk [17]. The greedy sparsification of the visibility graph allows us to easily route around obstacles. Our experimental results are visually appealing and convey a sense of abstraction and order.

In recent years trajectory data has become one of the main types of geographic data, and hence algorithmic tools to handle large quantities of trajectories are essential. A single trajectory is typically represented as a sequence of time-stamped points in the plane. In a collection of trajectories one wants to detect maximal groups of moving entities and their behaviour (merges and splits) over time. This information can be summarized in the trajectory grouping structure. Significantly extending the work of Buchin et al. [WADS 2013] into a realistic setting, we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly epsilon, where epsilon is the threshold distance that determines whether two entities are close enough to be in one group. In case the n entities move in a simple polygon along trajectories with tau vertices each we give an O(tau n^2) upper bound, which is tight in the worst case. In case of well-spaced obstacles we give an O(tau(n^2 + m lambda_4(n))) upper bound, where m is the total complexity of the obstacles, and lambda_s(n) denotes the maximum length of a Davenport-Schinzel sequence of n symbols of order s. In case of general obstacles we give an O(tau min(n^2 + m^3 lambda_4(n), n^2m^2)) upper bound. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.

We consider the problem of computing k shortest paths in a two-dimensional environment with polygonal obstacles, where the jth path, for 1 ≤ j ≤ k, is the shortest path in the free space that is also homotopically distinct from each of the first j – 1 paths. In fact, we consider a more general problem: given a source point s, construct a partition of the free space, called the kth shortest path map (k-SPM), in which the homotopy of the kth shortest path in a region has the same structure. Our main combinatorial result establishes a tight bound of Θ(k2h + kn) on the worst-case complexity of this map. We also describe an O((k3h + k2n) log (kn)) time algorithm for constructing the map. In fact, the algorithm constructs the jth map for every j ≤ k. Finally, we present a simple visibility-based algorithm for computing the k shortest paths between two fixed points. This algorithm runs in O(m log n + k) time and uses O(m + k) space, where m is the size of the visibility graph. This latter algorithm can be extended to compute k shortest simple (non-self-intersecting) paths, taking O(k2 m(m + kn) log (kn)) time. We invite the reader to play with our applet demonstrating k-SPMs [10].

Abstract Cartograms visualize quantitative data about a set of regions such as countries or states. There are several different types of cartograms and – for some – algorithms to automatically construct them exist. We focus on mosaic cartograms: cartograms that use multiples of simple tiles – usually squares or hexagons – to represent regions. Mosaic cartograms communicate well data that consist of, or can be cast into, small integer units (for example, electorial college votes). In addition, they allow users to accurately compare regions and can often maintain a (schematized) version of the input regions’ shapes. We propose the first fully automated method to construct mosaic cartograms. To do so, we first introduce mosaic drawings of triangulated planar graphs. We then show how to modify mosaic drawings into mosaic cartograms with low cartographic error while maintaining correct adjacencies between regions. We validate our approach experimentally and compare to other cartogram methods.

Hand-drawn schematized maps traditionally make extensive use of curves. However, there are few automated approaches for curved schematization; most previous work focuses on straight lines. We present a new algorithm for area-preserving curved schematization of territorial outlines. Our algorithm converts a simple polygon into a schematic crossing-free representation using circular arcs. We use two basic operations to iteratively replace consecutive arcs until the desired complexity is reached. Our results are not restricted to arcs ending at input vertices. The method can be steered towards different degrees of "curviness": we can encourage or discourage the use of arcs with a large central angle via a single parameter. Our method creates visually pleasing results even for very low output complexities. To evaluate the effectiveness of our design choices, we present a geometric evaluation of the resulting schematizations. Besides the geometric qualities of our algorithm, we also investigate the potential of curved schematization as a concept. We conducted an online user study investigating the effectiveness of curved schematizations compared to straight-line schematizations. While the visual complexity of curved shapes was judged higher than that of straight-line shapes, users generally preferred curved schematizations. We observed that curves significantly improved the ability of users to match schematized shapes of moderate complexity to their unschematized equivalents.

Hand-drawn schematized maps traditionally make extensive use of curves. However, there are few automated approaches for curved schematization most previous work focuses on straight lines. We present a new algorithm for area-preserving curved schematization of geographic outlines. Our algorithm converts a simple polygon into a schematic crossing-free representation using circular arcs. We use two basic operations to iteratively replace consecutive arcs until the desired complexity is reached. Our results are not restricted to arcs ending at input vertices. The method can be steered towards different degrees of 'curviness': we can encourage or discourage the use of arcs with a large central angle via a single parameter. Our method creates visually pleasing results even for very low output complexities. We conducted an online user study investigating the effectiveness of the curved schematizations compared to straight-line schematizations of equivalent complexity. While the visual complexity of the curved shapes was judged higher than those using straight lines, users generally preferred curved schematizations. We observed that curves significantly improved the ability of users to match schematized shapes of moderate complexity to their unschematized equivalents.

No abstract available.

We study the shortcut Fréchet distance, a natural variant of the Fréchet distance, that allows us to take shortcuts from and to any point along one of the curves. The classic Fréchet distance is a bottle-neck distance measure and hence quite sensitive to outliers. The shortcut Fréchet distance allows us to cut across outliers and hence produces more meaningful results when dealing with real world data. Driemel and Har-Peled recently described approximation algorithms for the restricted case where shortcuts have to start and end at input vertices. We show that, in the general case, the problem of computing the shortcut Fréchet distance is NP-hard. This is the first hardness result for a variant of the Fréchet distance between two polygonal curves in the plane. We also present two algorithms for the decision problem: a 3-approximation algorithm for the general case and an exact algorithm for the vertex-restricted case. Both algorithms run in O(n3 log n) time.

No abstract available.

We address some of the challenges in representing spatial data with a novel form of geometric abstraction-the stenomap. The stenomap comprises a series of smoothly curving linear glyphs that each represent both the boundary and the area of a polygon. We present an efficient algorithm to automatically generate these open, C1-continuous splines from a set of input polygons. Feature points of the input polygons are detected using the medial axis to maintain important shape properties. We use dynamic programming to compute a planar non-intersecting spline representing each polygon's base shape. The results are stylised glyphs whose appearance may be parameterised and that offer new possibilities in the 'cartographic design space'. We compare our glyphs with existing forms of geometric schematisation and discuss their relative merits and shortcomings. We describe several use cases including the depiction of uncertain model data in the form of hurricane track forecasting; minimal ink thematic mapping; and the depiction of continuous statistical data.

Associating the regions of a geographic subdivision with the cells of a grid is a basic operation that is used in various types of maps, like spatially ordered treemaps and OD maps. In these cases the regular shapes of the grid cells allows easy representation of extra information about the regions. The main challenge is to find an association that allows a user to find a region in the grid quickly. We call the representation of a set of regions as a grid a grid map.

We study two versions of the 2-center problem for moving points in the plane. Given a set P of n points, the Euclidean 2-center problem asks for two congruent disks of minimum size that together cover P; the rectilinear 2-center problem correspondingly asks for two congruent axis-aligned squares of minimum size that together cover P. Our methods work in the black-box KDS model, where we receive the locations of the points at regular time steps and we know an upper bound d_{max} on the maximum displacement of any point within one time step. We show how to maintain the rectilinear 2-center in amortized sub-linear time per time step, under certain assumptions on the distribution of the point set P. For the Euclidean 2-center we give a similar result: we can maintain in amortized sub-linear time (again under certain assumptions on the distribution) a (1+ε)-approximation of the optimal 2-center. In many cases---namely when the distance between the centers of the disks is relatively large or relatively small---the solution we maintain is actually optimal.

We present an algorithm for schematized focus maps. Focus maps integrate a high detailed, enlarged focus region continuously in a given base map. Recent methods integrate both with such low distortion that the focus region becomes hard to identify. We combine focus maps with partial schematization to display distortion of the context and to emphasize the focus region. Schematization visually conveys geographical accuracy, while not increasing map complexity. We extend the focus-map algorithm to incorporate geometric proximity relationships and show how to combine focus maps with schematization in order to cater to different use cases.

We present KelpFusion: a method for depicting set membership of items on a map or other visualization using continuous boundaries. KelpFusion is a hybrid representation that bridges hull techniques such as Bubble Sets and Euler diagrams and line- and graph-based techniques such as LineSets and Kelp Diagrams. We describe an algorithm based on shortest-path graphs to compute KelpFusion visualizations. Based on a single parameter, the shortest-path graph varies from the minimal spanning tree to the convex hull of a point set. Shortest-path graphs aim to capture the shape of a point set and smoothly adapt to sets of varying densities. KelpFusion fills enclosed faces based on a set of simple legibility rules. We present the results of a controlled experiment comparing KelpFusion to Bubble Sets and LineSets. We conclude that KelpFusion outperforms Bubble Sets both in accuracy and completion time and outperforms LineSets in completion time.

Abstract We present Kelp Diagrams, a novel method to depict set relations over points, i.e., elements with predefined positions. Our method creates schematic drawings and has been designed to take aesthetic quality, efficiency, and effectiveness into account. This is achieved by a routing algorithm, which links elements that are part of the same set by constructing minimum cost paths over a tangent visibility graph. There are two styles of Kelp Diagrams to depict overlapping sets, a nested and a striped style, each with its own strengths and weaknesses. We compare Kelp Diagrams with two existing methods and show that our approach provides a more consistent and clear depiction of both element locations and their set relations.

A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. These layouts are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists. Furthermore we show how to impose restrictions on the orientations of edges and junctions of the rectangular layout. Such an orientation-constrained layout, if it exists, may be constructed in polynomial time, and all orientation-constrained layouts may be listed in polynomial time per layout.

We present a data structure for ray shooting and insertion in the free space between disjoint polygonal obstacles with a total of $n$ vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses $O(n\log n)$ space and preprocessing time, and it supports $m$ successive ray shooting and insertion queries in $O((n+m)\log^2 n + m\log m)$ total time in the real RAM model of computation. We present two applications: (1) Our data structure supports efficient implementation of auto-partitions in the plane, that is, binary space partitions where each partition is done along the supporting line of an input segment. If $n$ input line segments are fragmented into $m$ pieces by an auto-partition, then it can now be implemented in $O(n\log^2n+m\log m)$ time. This improves the expected runtime of Patersen and Yao's classical randomized auto-partition algorithm for $n$ disjoint line segments in the plane to $O(n\log^2 n)$. (2) If we are given disjoint polygonal obstacles with a total of $n$ vertices in the plane, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The previously best implementation (with a semidynamic ray shooting data structure) requires $O(n^{3/2-\varepsilon/2})$ time using $O(n^{1+\varepsilon})$ space for any $\varepsilon>0$. Our data structure improves the runtime to $O(n\log^2 n)$.

Over the past decade, the kinetic-data-structures framework has become the standard in computational geometry for dealing with moving objects. A fundamental assumption underlying the framework is that the motions of the objects are known in advance. This assumption severely limits the applicability of KDSs. We study KDSs in the black-box model, which is a hybrid of the KDS model and the traditional time-slicing approach. In this more practical model we receive the position of each object at regular time steps and we have an upper bound on dmax, the maximum displacement of any point in one time step. We study the maintenance of the convex hull and the Delaunay triangulation of a planar point set P in the black-box model, under the following assumption on dmax: there is some constant k such that for any point p ∑ P the disk of radius dmax contains at most k points. We analyze our algorithms in terms of ∑k , the so-called k-spread of P. We show how to update the convex hull at each time step in O(k∑k log2 n) amortized time. For the Delaunay triangulation our main contribution is an analysis of the standard edge-flipping approach; we show that the number of flips is O(k2 ∑k2) at each time step.

An imprecise region, also called a vernacular region, is a region without a precise or administrative boundary. We present a new method to delineate imprecise regions from a set of points that are likely to lie inside the region. We use shortest-path graphs based on the squared Euclidean distance which capture the shape of region boundaries well. Shortest-path graphs naturally adapt to point sets of varying density, and they are always connected. As opposed to neighborhood graphs, they use a non-local criterion to determine which points to connect. Furthermore, shortest-path graphs can easily be extended to take geographic context into account by modeling context as "soft" obstacles. We present efficient algorithms to compute shortest-path graphs with or without geographic context. We experimentally evaluate the quality of the imprecise regions computed with our method. To fairly compare our results to those obtained by the common KDE approach, we also show how to integrate context into KDE by again using soft obstacles.

Directional relations are fundamental to spatial data queries, analysis and reasoning. Consequently there has been a significant amount of effort to determine directional relations between two regions. However, many existing methods do not perform well when the regions are neighboring or intertwined. In this paper we introduce a new model for directional relations which is based on a splitting line separating the two regions in question. We identify essential quality criteria for directional relation models and translate them into measurable properties of a given splitting line. We present an efficient algorithm that computes an optimal splitting line for two regions and perform extensive experiments. Our results show that the splitting line model captures directional relations very well and that it clearly outperforms existing approaches on pairs of neighboring or intertwined regions.

We introduce a local operation for polygons and subdivisions called an edge-move. Edge-moves do not change the edge orientations present in the input and are thus suitable for iterative simplification or even schematization. Based on edge-moves we present a new efficient method for area- and topology-preserving subdivision simplification. We show how to tailor this generic method towards the specific needs of building wall squaring and urban-area generalization. Our algorithm is guaranteed to make further progress on any subdivision that has two or more faces and/or reflex vertices. Furthermore, our method produces output of high visual quality and is able to generalize maps with ≈ 1.8 million edges in a few hours.

Flow maps are thematic maps that visualize the movement of objects, such as people or goods, between geographic regions. One or more sources are connected to several targets by lines whose thickness corresponds to the amount of flow between a source and a target. Good flow maps reduce visual clutter by merging (bundling) lines smoothly and by avoiding self-intersections. Most flow maps are still drawn by hand and only few automated methods exist. Some of the known algorithms do not support edge-bundling and those that do, cannot guarantee crossing-free flows. We present a new algorithmic method that uses edge-bundling and computes crossing-free flows of high visual quality. Our method is based on so-called spiral trees, a novel type of Steiner tree which uses logarithmic spirals. Spiral trees naturally induce a clustering on the targets and smoothly bundle lines. Our flows can also avoid obstacles, such as map features, region outlines, or even the targets. We demonstrate our approach with extensive experiments.

Proportional symbol maps visualize numerical data associated with point locations by placing a scaled symbol—typically an opaque disk or square—at the corresponding point on a map. The area of each symbol is proportional to the numerical value associated with its location. Every visually meaningful proportional symbol map will contain at least some overlapping symbols. These need to be drawn in such a way that the user can still judge their relative sizes accurately. We identify two types of suitable drawings: physically realizable drawings and stacking drawings. For these we study the following two problems: Max-Min—maximize the minimum visible boundary length of each symbol—and Max-Total—maximize the total visible boundary length over all symbols. We show that both problems are NP-hard for physically realizable drawings. Max-Min can be solved in O(n 2log n) time for stacking drawings, which can be improved to O(nlog n) time when the input has certain properties. We also implemented several methods to compute stacking drawings: our solution to the Max-Min problem performs best on the data sets considered.

Statistical data associated with geographic regions is nowadays globally available in large amounts and hence automated methods to visually display these data are in high demand. There are several well-established thematic map types for quantitative data on the ratio-scale associated with regions: choropleth maps, cartograms, and proportional symbol maps. However, all these maps suffer from limitations, especially if large data values are associated with small regions. To overcome these limitations, we propose a novel type of quantitative thematic map, the necklace map. In a necklace map, the regions of the underlying two-dimensional map are projected onto intervals on a one-dimensional curve (the necklace) that surrounds the map regions. Symbols are scaled such that their area corresponds to the data of their region and placed without overlap inside the corresponding interval on the necklace. Necklace maps appear clear and uncluttered and allow for comparatively large symbol sizes. They visualize data sets well which are not proportional to region sizes. The linear ordering of the symbols along the necklace facilitates an easy comparison of symbol sizes. One map can contain several nested or disjoint necklaces to visualize clustered data. The advantages of necklace maps come at a price: the association between a symbol and its region is weaker than with other types of maps. Interactivity can help to strengthen this association if necessary. We present an automated approach to generate necklace maps which allows the user to interactively control the final symbol placement. We validate our approach with experiments using various data sets and maps.

No abstract available.

A rectangular layout is a partition of a rectangle into a finite set of interior-disjoint rectangles. They are used as rectangular cartograms in cartography, as floorplans in building architecture and VLSI design, and as graph drawings. Often areas are associated with the rectangles of a rectangular layout and it is desirable for one rectangular layout to represent several area assignments. A layout is area-universal if any assignment of areas to rectangles can be realized by a combinatorially equivalent rectangular layout. We identify a simple necessary and sufficient condition for a rectangular layout to be area-universal: a rectangular layout is area-universal if and only if it is one-sided. We also investigate similar questions for perimeter assignments. The adjacency requirements for the rectangles of a rectangular layout can be specified in various ways, most commonly via the dual graph of the layout. We show how to find an area-universal layout for a given set of adjacency requirements whenever such a layout exists.

We present a data structure for ray shooting-and-insertion in the free space among disjoint polygonal obstacles with a total of $n$ vertices in the plane, where each ray starts at the boundary of some obstacle. The portion of each query ray between the starting point and the first obstacle hit is inserted permanently as a new obstacle. Our data structure uses O(n log n) space and preprocessing time, and it supports m successive ray shooting-and-insertion queries in O(n log2 n + m log m) total time. We present two applications for our data structure: (1) Our data structure supports efficient implementation of auto-partitions in the plane i.e. binary space partitions where each partition is done along the supporting line of an input segment. If n input line segments are fragmented into m pieces by an auto-partition, then it can now be implemented in O(n log2n+m log m) time. This improves the expected runtime of Patersen and Yao's classical randomized auto-partition algorithm for n disjoint line segments to O(n log2 n). (2) If we are given disjoint polygonal obstacles with a total of n vertices in the plane, a permutation of the reflex vertices, and a half-line at each reflex vertex that partitions the reflex angle into two convex angles, then the folklore convex partitioning algorithm draws a ray emanating from each reflex vertex in the prescribed order in the given direction until it hits another obstacle, a previous ray, or infinity. The previously best implementation (with a semi-dynamic ray shooting data structure) requires O(n3/2-ε/2) time using O(n1+ε) space. Our data structure improves the runtime to O(n log2 n).

We design compact and responsive kinetic data structures for detecting collisions between n convex fat objects in 3-dimensional space that can have arbitrary sizes. Our main results are: If the objects are 3-dimensional balls that roll on a plane, then we can detect collisions with a KDS of size O ( n log n ) that can handle events in O (log 2 n ) time. This structure processes O ( n 2 ) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects are convex fat 3-dimensional objects of constant complexity that are free-flying in ℝ 3 , then we can detect collisions with a KDS of O ( n log 6 n ) size that can handle events in O (log 7 n ) time. This structure processes O ( n 2 ) events in the worst case, assuming that the objects follow constant-degree algebraic trajectories. If the objects have similar sizes then the size of the KDS becomes O ( n ) and events can be handled in O (log n ) time.

We show that the vertices of any plane graph in which every face is incident to at least g vertices can be colored by ⌊(3g−5)/4⌋ colors so that every color appears in every face. This is nearly tight, as there are plane graphs where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g+1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in ℘ for k=2 and is $\mathcal{NP}$ -complete for k=3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in ℘, and for the others it is $\mathcal{NP}$ -complete.

We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of n points in $\mathbb{R}^d$. We show that a rank-based kd-tree, like an ordinary kd-tree, supports orthogonal range queries in $O(n^{1-1/d}+k)$ time, where k is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the kinetic data structure (KDS) processes $O(n^2)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in $O(\log n)$ time, and each point is involved in $O(1)$ certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees, for sets of points in $\mathbb{R}^2$. Rank-based longest-side kd-trees can be kinetized efficiently as well, and like longest-side kd-trees, they support $\varepsilon$-approximate nearest-neighbor, $\varepsilon$-approximate farthest-neighbor, and $\varepsilon$-approximate range queries with convex ranges in $O((1/\epsilon)\log^2n)$ time. The KDS processes $O(n^3\log n)$ events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in $O(\log^2n)$ time, and each point is involved in $O(\log n)$ certificates.

We show that the vertices of any plane graph in which every face is of size at least g can be colored by (3g Àý 5)=4 colors so that every color appears in every face. This is nearly tight, as there are plane graphs that admit no vertex coloring of this type with more than (3g+1)=4 colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by 3 colors in which all colors appear in every face is NP-complete even for graphs in which all faces are of size 3 or 4 only. If all faces are of size 3 this can be decided in polynomial time.

Road network data is often incomplete, making it hard to perform network analysis. This paper discusses the problem of extending partial road networks with reasonable links, using the concept of dilation (also known as crow flight conversion coefficient). To this end, we study how to connect a point (relevant location) inside a polygon (face of the known part of the road network) to the boundary so that the dilation from that point to any point on the boundary is not too large. We provide algorithms and heuristics, and give a computational and experimental analysis.

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points. We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes. An O(n d ) time and O(n d−1) space algorithm computes undirected depth of all points in d dimensions. Properties of undirected depth lead to an O(nlog 2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions, which has been improved to an O(nlog n) time algorithm by Langerman and Steiger (Discrete Comput. Geom. 30(2):299–309, [2003]). Furthermore, we describe the structure of depth in the plane and higher dimensions, leading to various other geometric and algorithmic results.

We propose a simple variant of kd-trees, called rank-based kd-trees, for sets of points in Rd. We show that a rank-based kd-tree, like an ordinary kd-tree, supports range search queries in O(n1−1/d+ k) time, where k is the output size. The main advantage of rank-based kd-trees is that they can be efficiently kinetized: the KDS processes O(n2) events in the worst case, assuming that the points follow constant-degree algebraic trajectories, each event can be handled in O(logn) time, and each point is involved in O(1) certificates. We also propose a variant of longest-side kd-trees, called rank-based longest-side kd-trees (RBLS kd-trees, for short), for sets of points in R2. RBLS kd-trees can be kinetized efficiently as well and like longest-side kd-trees, RBLS kd-trees support nearest-neighbor, farthest-neighbor, and approximate range search queries in O((1/ε) log2 n) time. The KDS processes O(n3 logn) events in the worst case, assuming that the points follow constant-degree algebraic trajectories; each event can be handled in O(log2 n) time, and each point is involved in O(logn) certificates. Background. Due to the increased availability of GPS systems and to other technological advances, motion data is becoming more and more available in a variety of application areas: air-traffic control,

A cartogram is a thematic map that visualizes statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic variable, for example, population. We present an algorithm for constructing rectilinear cartograms (each region is represented by a rectilinear polygon) with zero cartographic error and correct region adjacencies, and we test our algorithm on various data sets. It produces regions of very small complexity---in fact, most regions are rectangles---while still ensuring both exact areas and correct adjacencies for all regions.Our algorithm uses a novel subroutine that is interesting in its own right, namely a polynomial-time algorithm for computing optimal binary space partitions (BSPs) for rectilinear maps. This algorithm works for a general class of optimality criteria, including size and depth. We use this generality in our application to computing cartograms, where we apply a dedicated cost function leading to BSP's amenable to the constructing of high-quality cartograms.

Cartograms, which are also referred to as value-by-area maps, are a useful and intuitive way to visualize statistical data about a set of regions like countries, states or provinces. The size of a region in a cartogram corresponds to a particular geographic variable [1]. Since the sizes of the regions are not their true sizes they generally cannot keep both their shape and their adjacencies. A good cartogram, however, preserves the recognizability in some way. Globally speaking, there are three types of cartogram. The standard type (the contiguous area cartogram) has deformed regions so that the desired sizes can be obtained and the adjacencies kept. Algorithms for such cartograms are described in [2, 3, 6, 9]. The second type of cartogram is the non-contiguous area cartogram [7]. The regions have the true shape, but are scaled down and generally do not touch anymore. The third type of cartogram is the rectangular cartogram, introduced by Raisz in 1934 [8], where each region is represented by a rectangle. This has the advantage that the sizes (area) of the regions can be estimated much better than with the first two types. Tobler states in a recent survey, “Thirty-five years of computer cartograms” [10], that none of the existing cartogram algorithms are capable of generating rectangular cartograms. However, even more recently the last two authors of this abstract presented the first algorithms for rectangular cartogram construction [11].

We describe how to construct and kinetically maintain a tessellation of the free space between a collection of k disjoint simple polygonal objects with a total of N vertices, R of which are reflex. Our linear size tessellation consists of pseudo-triangles and has the following properties: (i) it contains disjoint outer hierarchical representations of all objects where the size of the outer boundary of these representations is proportional to a minimum link separator for the objects, and (ii) any line segment in the free space intersects at most O((k + log R) log N) pseudo-triangles (each of constant size).We maintain our tessellation by using the Kinetic Data Structure (KDS) framework. Our structure is compact, maintaining an active set of certificates whose number is linear in the size of a minimum link subdivision for the objects. It is also responsive; on the failure of a certificate invariants can be restored in time logarithmic in the total number of vertices. While its efficiency is difficult to establish precisely, it is shown that at most O(k + κmaxlog R)log N events happen during straight line motion of one object A in the context of k (fixed) others, where κmax denotes the maximum size of the minimum link polygon separating object A from the rest, during the motion.Furthermore, ray shooting queries (that use point location) can be answered in O((k + log R) log N) time for rays with arbitrary direction.

Many graphics libraries support triangle strips because they can significantly speed up the display of a triangulated surface, such as a TIN terrain model. We show that spanning trees based on visibility give a simple and effective way to generate good triangle strips for TINs.

We design a simple and elegant kinetic data structure for detecting collisions between simple but not necessarily convex polygonal objects in motion in the plane.Our structure is compact, maintaining an active set of certificates whose number is proportional to a minimumsize set of separating polygons for the objects.It is also responsive; on the failure of a certificate invariants can be restored in time logarithmic in the total number of object vertices.It is difficult to characterize the efficiency of our structure for lack of a canonical definition of external events.Nevertheless we give an easy upper bound on the worst case number of certificate failures. IntroductionAlgorithms and data structures for long-running simulations or continuous monitoring applications do not always fit into the style of big-O asymptotic analysis that is based on batch processing (input, processing, output).The alternatives of amortized analysis, competitive analysis, or experimental evaluation do not always suit.Amortized analysis can hide unacceptably large per-operation costs, competitive analysis is difficult even on well-established algorithms like LRU page replacement, and experimental evaluations are difficult to compare and can obscure the portable ideas and concepts with non-portable implementation details.For this reason, we find the "kinetic data structures" (KDS) framework, which supports the design and analysis of algorithms and data structures that monitor properties of data in motion [4,5], to be an exciting development in computational geometry.A kinetic data structure contains a set of certificates that constitutes a proof °

We investigate algorithmic questions that arise in the statistical problem of computing lines or hyperplanes of maximum regression depth among a set of n points.We work primarily with a dual representation and find points of maximum undirected depth in an arrangement of lines or hyperplanes.An O(nd) time and space algorithm computes directed depth of all points in d dimensions.Properties of undirected depth lead to an O(n log2 n) time and O(n) space algorithm for computing a point of maximum depth in two dimensions.We also give approximation algorithms for hyperplane arrangements and degenerate line arrangements.