Eurovis: Eurographics Conference on Visualization

Permanent URI for this community

https://diglib.eg.org/handle/10.2312/392

Browse

Browsing Eurovis: Eurographics Conference on Visualization by Subject "Algorithms"

Now showing 1 - 4 of 4
  • Thumbnail Image
    Item
    Location-dependent Generalization of Road Networks Based on Equivalent Destinations
    (The Eurographics Association and John Wiley & Sons Ltd., 2016) Dijk, Thomas C. van; Haunert, Jan-Henrik; Oehrlein, Johannes; Kwan-Liu Ma and Giuseppe Santucci and Jarke van Wijk
    Suppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge-weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear-time algorithm to compute the minimum-cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus-and-context map generalization. When contracting shortestpath trees in a geographic network, the computed clustering additionally provides a constant-factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps.
  • Thumbnail Image
    Item
    Streaming Approach to In Situ Selection of Key Time Steps for Time-Varying Volume Data
    (The Eurographics Association and John Wiley & Sons Ltd., 2022) Wu, Mengxi; Chiang, Yi-Jen; Musco, Christopher; Borgo, Rita; Marai, G. Elisabeta; Schreck, Tobias
    Key time steps selection, i.e., selecting a subset of most representative time steps, is essential for effective and efficient scientific visualization of large time-varying volume data. In particular, as computer simulations continue to grow in size and complexity, they often generate output that exceeds both the available storage capacity and bandwidth for transferring results to storage, making it indispensable to save only a subset of time steps. At the same time, this subset must be chosen so that it is highly representative, to facilitate post-processing and reconstruction with high fidelity. The key time steps selection problem is especially challenging in the in situ setting, where we can only process data in one pass in an online streaming fashion, using a small amount of main memory and fast computation. In this paper, we formulate the problem as that of optimal piece-wise linear interpolation. We first apply a method from numerical linear algebra to compute linear interpolation solutions and their errors in an online streaming fashion. Using that method as a building block, we can obtain a global optimal solution for the piece-wise linear interpolation problem via a standard dynamic programming (DP) algorithm. However, this approach needs to process the time steps in multiple passes and is too slow for the in situ setting. To address this issue, we introduce a novel approximation algorithm, which processes time steps in one pass in an online streaming fashion, with very efficient computing time and main memory space both in theory and in practice. The algorithm is suitable for the in situ setting. Moreover, we prove that our algorithm, which is based on a greedy update rule, has strong theoretical guarantees on the approximation quality and the number of time steps stored. To the best of our knowledge, this is the first algorithm suitable for in situ key time steps selection with such theoretical guarantees, and is the main contribution of this paper. Experiments demonstrate the efficacy of our new techniques.
  • Thumbnail Image
    Item
    Vector Field k-Means: Clustering Trajectories by Fitting Multiple Vector Fields
    (The Eurographics Association and Blackwell Publishing Ltd., 2013) Ferreira, Nivan; Klosowski, James T.; Scheidegger, Carlos E.; Silva, Cláudio T.; B. Preim, P. Rheingans, and H. Theisel
    Scientists study trajectory data to understand trends in movement patterns, such as human mobility for traffic analysis and urban planning. In this paper, we introduce a novel trajectory clustering technique whose central idea is to use vector fields to induce a notion of similarity between trajectories, letting the vector fields themselves define and represent each cluster. We present an efficient algorithm to find a locally optimal clustering of trajectories into vector fields, and demonstrate how vector-field k-means can find patterns missed by previous methods. We present experimental evidence of its effectiveness and efficiency using several datasets, including historical hurricane data, GPS tracks of people and vehicles, and anonymous cellular radio handoffs from a large service provider.
  • No Thumbnail Available
    Item
    Visual Analysis of Confocal Raman Spectroscopy Data using Cascaded Transfer Function Design
    (The Eurographics Association and John Wiley & Sons Ltd., 2017) Schikora, Christoph Markus; Plack, Markus; Bornemann, Rainer; Bolívar, Peter Haring; Kolb, Andreas; Heer, Jeffrey and Ropinski, Timo and van Wijk, Jarke
    2D Confocal Raman Microscopy (CRM) data consist of high dimensional per-pixel spectral data of 1000 bands and allows for complex spectral and spatial-spectral analysis tasks, i.e., in material discrimination, material thickness, and spatial material distributions. Currently, simple integral methods are commonly applied as visual analysis solutions to CRM data which exhibit restricted discrimination power in various regards. In this paper we present a novel approach for the visual analysis of 2D multispectral CRM data using multi-variate visualization techniques. Due to the large amount of data and the demand of an explorative approach without a-priori restriction, our system allows for arbitrary interactive (de)selection of varaibles w/o limitation and an unrestricted online definition/construction of new, combined properties. Our approach integrates CRM specific quantitative measures and handles material-related features for mixed materials in a quantitative manner. Technically, we realize the online definition/construction of new, combined properties as semi-automatic, cascaded, 1D and 2D multidimensional transfer functions (MD-TFs). By interactively incorporating new (raw or derived) properties, the dimensionality of the MD-TF space grows during the exploration procedure and is virtually unlimited. The final visualization is achieved by an enhanced color mixing step which improves saturation and contrast.