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 - 2 of 2
  • 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
    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.