Route-preserving Road Network Generalization

Mees Van De Kerkhof; Irina Kostitsyna; Marc Van Kreveld; Maarten Löffler; Tim Ophelders

doi:10.1145/3397536.3422234

Route-preserving Road Network Generalization

Mees Van De Kerkhof
, Irina Kostitsyna
, Marc Van Kreveld
, Maarten Löffler
, Tim Ophelders

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

2 Citations (Scopus)

Abstract

We investigate a data-driven approach for road network generalization, where the input is a road network and a collection of routes or trajectories on these roads. The aim is to select a subset of the road network in which many routes of the collection are fully preserved. We formulate the problem and present several heuristic versions of it, as the general problem is NP-hard. We show the outcome of the versions on a data set for comparison purposes.

Original language	English
Title of host publication	Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020
Editors	Chang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn Newsam, Li Xiong
Publisher	Association for Computing Machinery, Inc.
Pages	381-384
Number of pages	4
ISBN (Electronic)	9781450380195
DOIs	https://doi.org/10.1145/3397536.3422234
Publication status	Published - 3 Nov 2020
Event	28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 - Virtual, Online, United States Duration: 3 Nov 2020 → 6 Nov 2020

Conference

Conference	28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020
Country/Territory	United States
City	Virtual, Online
Period	3/11/20 → 6/11/20

Funding

This research was started at the AGA workshop, January 2020, in Langbroek (NL). M.v.d.K., M.v.K., and M.L. are supported by The Netherlands Organisation for Scientific Research on the Commit2Data project “Geometric Algorithms for the Analysis and Visualization of Heterogeneous Spatio-temporal Data” (no. 628.011.005). M.L. is supported by The Netherlands Organisation for Scientific Research on grant no. 614.001.504. The authors thank HERE Technologies for providing data.

Keywords

algorithms
data-driven
map generalization
optimization
road networks
trajectories

Access to Document

10.1145/3397536.3422234

Cite this

Van De Kerkhof, M., Kostitsyna, I., Van Kreveld, M., Löffler, M., & Ophelders, T. (2020). Route-preserving Road Network Generalization. In C.-T. Lu, F. Wang, G. Trajcevski, Y. Huang, S. Newsam, & L. Xiong (Eds.), Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 (pp. 381-384). Association for Computing Machinery, Inc.. https://doi.org/10.1145/3397536.3422234

Van De Kerkhof, Mees ; Kostitsyna, Irina ; Van Kreveld, Marc et al. / Route-preserving Road Network Generalization. Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020. editor / Chang-Tien Lu ; Fusheng Wang ; Goce Trajcevski ; Yan Huang ; Shawn Newsam ; Li Xiong. Association for Computing Machinery, Inc., 2020. pp. 381-384

@inproceedings{53d5383d721144f4957cb0742da867fd,

title = "Route-preserving Road Network Generalization",

abstract = "We investigate a data-driven approach for road network generalization, where the input is a road network and a collection of routes or trajectories on these roads. The aim is to select a subset of the road network in which many routes of the collection are fully preserved. We formulate the problem and present several heuristic versions of it, as the general problem is NP-hard. We show the outcome of the versions on a data set for comparison purposes. ",

keywords = "algorithms, data-driven, map generalization, optimization, road networks, trajectories",

author = "\{Van De Kerkhof\}, Mees and Irina Kostitsyna and \{Van Kreveld\}, Marc and Maarten L{\"o}ffler and Tim Ophelders",

year = "2020",

month = nov,

day = "3",

doi = "10.1145/3397536.3422234",

language = "English",

pages = "381--384",

editor = "Chang-Tien Lu and Fusheng Wang and Goce Trajcevski and Yan Huang and Shawn Newsam and Li Xiong",

booktitle = "Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020",

publisher = "Association for Computing Machinery, Inc.",

address = "United States",

note = "28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020 ; Conference date: 03-11-2020 Through 06-11-2020",

}

Van De Kerkhof, M, Kostitsyna, I, Van Kreveld, M, Löffler, M & Ophelders, T 2020, Route-preserving Road Network Generalization. in C-T Lu, F Wang, G Trajcevski, Y Huang, S Newsam & L Xiong (eds), Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020. Association for Computing Machinery, Inc., pp. 381-384, 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020, Virtual, Online, United States, 3/11/20. https://doi.org/10.1145/3397536.3422234

Route-preserving Road Network Generalization. / Van De Kerkhof, Mees; Kostitsyna, Irina; Van Kreveld, Marc et al.
Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020. ed. / Chang-Tien Lu; Fusheng Wang; Goce Trajcevski; Yan Huang; Shawn Newsam; Li Xiong. Association for Computing Machinery, Inc., 2020. p. 381-384.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Route-preserving Road Network Generalization

AU - Van De Kerkhof, Mees

AU - Kostitsyna, Irina

AU - Van Kreveld, Marc

AU - Löffler, Maarten

AU - Ophelders, Tim

PY - 2020/11/3

Y1 - 2020/11/3

N2 - We investigate a data-driven approach for road network generalization, where the input is a road network and a collection of routes or trajectories on these roads. The aim is to select a subset of the road network in which many routes of the collection are fully preserved. We formulate the problem and present several heuristic versions of it, as the general problem is NP-hard. We show the outcome of the versions on a data set for comparison purposes.

AB - We investigate a data-driven approach for road network generalization, where the input is a road network and a collection of routes or trajectories on these roads. The aim is to select a subset of the road network in which many routes of the collection are fully preserved. We formulate the problem and present several heuristic versions of it, as the general problem is NP-hard. We show the outcome of the versions on a data set for comparison purposes.

KW - algorithms

KW - data-driven

KW - map generalization

KW - optimization

KW - road networks

KW - trajectories

UR - https://www.scopus.com/pages/publications/85097259681

U2 - 10.1145/3397536.3422234

DO - 10.1145/3397536.3422234

M3 - Conference contribution

AN - SCOPUS:85097259681

SP - 381

EP - 384

BT - Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020

A2 - Lu, Chang-Tien

A2 - Wang, Fusheng

A2 - Trajcevski, Goce

A2 - Huang, Yan

A2 - Newsam, Shawn

A2 - Xiong, Li

PB - Association for Computing Machinery, Inc.

T2 - 28th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020

Y2 - 3 November 2020 through 6 November 2020

ER -

Van De Kerkhof M, Kostitsyna I, Van Kreveld M, Löffler M, Ophelders T. Route-preserving Road Network Generalization. In Lu CT, Wang F, Trajcevski G, Huang Y, Newsam S, Xiong L, editors, Proceedings of the 28th International Conference on Advances in Geographic Information Systems, SIGSPATIAL GIS 2020. Association for Computing Machinery, Inc. 2020. p. 381-384 doi: 10.1145/3397536.3422234

Route-preserving Road Network Generalization

Abstract

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this