Location-dependent Generalization of Road Networks Based on Equivalent Destinations

Simple item page
dc.contributor.authorDijk, Thomas C. vanen_US
dc.contributor.authorHaunert, Jan-Henriken_US
dc.contributor.authorOehrlein, Johannesen_US
dc.contributor.editorKwan-Liu Ma and Giuseppe Santucci and Jarke van Wijken_US
dc.date.accessioned2016-06-09T09:33:04Z
dc.date.available2016-06-09T09:33:04Z
dc.date.issued2016en_US
dc.description.abstractSuppose 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.en_US
dc.description.number3en_US
dc.description.sectionheadersGeospatial Data Visualizationen_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume35en_US
dc.identifier.doi10.1111/cgf.12921en_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages451-460en_US
dc.identifier.urihttps://doi.org/10.1111/cgf.12921en_US
dc.identifier.urihttps://diglib.eg.org:443/handle/10
dc.publisherThe Eurographics Association and John Wiley & Sons Ltd.en_US
dc.subjectKeywordsen_US
dc.subjectclusteringen_US
dc.subjectsimplificationen_US
dc.subjectmap generalizationen_US
dc.subjecten_US
dc.subjectI.2.1 [ARTIFICIAL INTELLIGENCE]en_US
dc.subjectApplications and Expert Systemsen_US
dc.subjectCartographyen_US
dc.subjecten_US
dc.subjectI.5.3 [PATTERN RECOGNITION]en_US
dc.subjectClusteringen_US
dc.subjectAlgorithmsen_US
dc.titleLocation-dependent Generalization of Road Networks Based on Equivalent Destinationsen_US
Files
Collections
35-Issue 3
EuroVis16: Eurographics Conference on Visualization