research-article

Road segment selection with strokes and stability

Authors:

T. C. van Dijk,

J. SpoerhaseAuthors Info & Claims

MapInteract '13: Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction

Pages 72 - 77

https://doi.org/10.1145/2534931.2534936

Published: 05 November 2013 Publication History

Abstract

In order to visualize a road network without producing visual clutter, a subset of all road segments needs to be selected. Many algorithms for road segment selection are based on a relevance score for edges in a network (for example betweenness centrality) and proceed by taking a greedy selection based on these weights. This can give dissatisfactory results. In order to improve readability, we introduce a stroke-based constraint and provide an efficient dynamic program that makes an optimal selection given this constraint. Next, we consider the computation of animated road selections from changing edge weights (for example a focus area that follows a moving user). Handling each time step of the animation individually can lead to distracting flickering effects. Here we introduce an optimization objective to achieve a more stable selection and provide a polynomial-time algorithm for solving it. While separately solvable in polynomial time, we show that the combination of the stroke constraints and stability optimization is NP-hard.

References

[1]

K. Been, M. Nöllenburg, S.-H. Poon, and A. Wolff. Optimizing active ranges for consistent dynamic map labeling. Computational Geometry, 43(3):312--328, 2010.

Digital Library

[2]

M. Blum, R. W. Floyd, V. Pratt, R. L. Rivest, and R. E. Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448--461, 1973.

Digital Library

[3]

T. C. v. Dijk and J.-H. Haunert. A probabilistic model for road selection in mobile maps. In Proc. 12th Internat. Sympos. Web and Wireless Geographical Information Systems, volume 7820 of Lecture Notes in Computer Science, pages 214--222. Springer-Verlag, Berlin, Germany, 2013.

Digital Library

[4]

M. Fischetti, H. W. Hamacher, K. Jørnsten, and F. Maffioli. Weighted k-cardinality trees: Complexity and polyhedral structure. Networks, 24(1):11--21, 1994.

[5]

A. Gemsa, B. Niedermann, and M. Nöllenburg. Trajectory-based dynamic map labeling. In Proc. 29th European Workshop Computational Geometry (EuroCG'13), 2013.

[6]

A. Gemsa, M. Nöllenburg, and I. Rutter. Consistent labeling of rotating maps. In Proc. 12th Internat. Sympos. Algorithms and Data Structures (WADS'11), volume 6844 of Lecture Notes in Computer Science, pages 451--462. Springer-Verlag, Berlin, Germany, 2011.

Digital Library

[7]

D. S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6):341--343, 1975.

Digital Library

[8]

B. Jiang. Ranking spaces for predicting human movement in an urban environment. International Journal of Geographical Information Science, 23(7):823--837, 2009.

Digital Library

[9]

B. Jiang and C. Claramunt. A structural approach to the model generalization of an urban street network. Geoinformatica, 8(2):157--171, 2004.

Digital Library

[10]

J. Kleinberg and E. Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 2005.

Digital Library

[11]

J. Kopf, M. Agrawala, D. Bargeron, D. Salesin, and M. Cohen. Automatic generation of destination maps. ACM Transactions on Graphics, 29(6):158:1--158:12, 2010.

Digital Library

[12]

W. A. Mackaness and M. K. Beard. Use of graph theory to support map generalization. Cartography and Geographic Information Systems, 20:210--221, 1993.

[13]

F. Schmid, C. Kuntzsch, S. Winter, A. Kazerani, and B. Preisig. Situated local and global orientation in mobile you-are-here maps. In Proc. 12th Internat. Conf. Human Computer Interaction with Mobile Devices and Services, MobileHCI '10, pages 83--92. ACM, 2010.

Digital Library

[14]

R. C. Thomson and R. Brooks. Exploiting perceptual grouping for map analysis, understanding and generalization: The case of road and river networks. In Selected Papers from the Fourth Internat. Workshop Graphics Recognition Algorithms and Applications, GREC '01, pages 148--157. Springer-Verlag, Berlin, Germany, 2002.

Digital Library

[15]

B. Yang, X. Luan, and Q. Li. Generating hierarchical strokes from urban street networks based on spatial pattern recognition. International Journal of Geographical Information Science, 25(12):2025--2050, 2011.

[16]

Q. Zhang. Road network generalization based on connection analysis. In Developments in Spatial Data Handling -- Proc. 11th Internat. Symposium Spatial Data Handling, pages 343--353, 2005.

Cited By

Gedicke SOehrlein JHaunert J(2021)Aggregating land-use polygons considering line features as separating map elementsCartography and Geographic Information Science10.1080/15230406.2020.1851613(1-16)Online publication date: 26-Jan-2021
https://doi.org/10.1080/15230406.2020.1851613
Chimani Mvan Dijk THaunert JHuang YSchneider MGertz MKrumm JSankaranarayanan J(2014)How to eat a graphProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2666310.2666414(243-252)Online publication date: 4-Nov-2014
https://dl.acm.org/doi/10.1145/2666310.2666414

Index Terms

Road segment selection with strokes and stability

Recommendations

Fuzzy stroke analysis of Devnagari handwritten characters

Devnagari script is a major script of India widely used for various languages. In this work, we propose a fuzzy stroke-based technique for analyzing handwritten Devnagari characters. After preprocessing, the character is segmented in strokes using our ...
A Method of Recognition of Arabic Cursive Handwriting

In spite of the progress of machine recognition techniques of Latin, Kana, and Chinese characters over the two past decades, the machine recognition of Arabic characters has remained almost untouched. In this correspondence, a structural recognition ...
Effect of Road Adhesion Coefficient on Tractor-Semitrailer Cornering Braking Stability
MECS '15: Proceedings of the 2015 International Conference on Mechanical Engineering and Control Systems

A dynamic model of tractor-semitrailer cornering braking was established in this paper, and the accuracy of the model was verified by real vehicle test. By model simulation of the cornering braking process, different road adhesion coefficient such as ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MapInteract '13: Proceedings of the 1st ACM SIGSPATIAL International Workshop on MapInteraction

November 2013

97 pages

ISBN:9781450325363

DOI:10.1145/2534931

Program Chairs:
Falko Schmid
University of Bremen, Germany
,
Chris Kray
University of Muenster, Germany

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSPATIAL: ACM Special Interest Group on Spatial Information

In-Cooperation

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Deutsche Forschungsgemeinschaft

Conference

SIGSPATIAL'13

Sponsor:

SIGSPATIAL

SIGSPATIAL'13: 21st SIGSPATIAL International Conference on Advances in Geographic Information Systems

November 5, 2013

Florida, Orlando

Acceptance Rates

MapInteract '13 Paper Acceptance Rate 17 of 20 submissions, 85%;

Overall Acceptance Rate 17 of 20 submissions, 85%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
97
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gedicke SOehrlein JHaunert J(2021)Aggregating land-use polygons considering line features as separating map elementsCartography and Geographic Information Science10.1080/15230406.2020.1851613(1-16)Online publication date: 26-Jan-2021
https://doi.org/10.1080/15230406.2020.1851613
Chimani Mvan Dijk THaunert JHuang YSchneider MGertz MKrumm JSankaranarayanan J(2014)How to eat a graphProceedings of the 22nd ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems10.1145/2666310.2666414(243-252)Online publication date: 4-Nov-2014
https://dl.acm.org/doi/10.1145/2666310.2666414

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents