{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T02:52:45Z","timestamp":1760237565803,"version":"build-2065373602"},"reference-count":16,"publisher":"MDPI AG","issue":"7","license":[{"start":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T00:00:00Z","timestamp":1656288000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Austrian Science Fund","award":["I 5270-N"],"award-info":[{"award-number":["I 5270-N"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We show that the so-called motorcycle graph of a planar polygon can be constructed by a randomized incremental algorithm that is simple and experimentally fast. Various test data are given, and a clustering method for speeding up the construction is proposed.<\/jats:p>","DOI":"10.3390\/a15070225","type":"journal-article","created":{"date-parts":[[2022,6,27]],"date-time":"2022-06-27T22:31:14Z","timestamp":1656369074000},"page":"225","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Incremental Construction of Motorcycle Graphs"],"prefix":"10.3390","volume":"15","author":[{"given":"Franz","family":"Aurenhammer","sequence":"first","affiliation":[{"name":"Institute for Theoretical Computer Science, Graz University of Technology, 8010 Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christoph","family":"Ladurner","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Computer Science, Graz University of Technology, 8010 Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Steinkogler","sequence":"additional","affiliation":[{"name":"Institute for Theoretical Computer Science, Graz University of Technology, 8010 Graz, Austria"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2022,6,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Aurenhammer, F., Klein, R., and Lee, D.T. (2013). Voronoi Diagrams and Delaunay Triangulations, World Scientific.","DOI":"10.1142\/8685"},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"569","DOI":"10.1007\/PL00009479","article-title":"Raising roofs, crashing cycles, and playing pool: Applications of a data structure for finding pairwise interactions","volume":"22","author":"Eppstein","year":"1999","journal-title":"Discrete Comput. Geom."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2898961","article-title":"A Faster Algorithm for Computing Straight Skeletons","volume":"12","author":"Cheng","year":"2016","journal-title":"ACM Trans. Algorithms"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s00453-006-1229-7","article-title":"Motorcycle graphs and straight skeletons","volume":"47","author":"Cheng","year":"2007","journal-title":"Algorithmica"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"492","DOI":"10.1007\/s00454-014-9625-2","article-title":"A faster algorithm for computing motorcycle graphs","volume":"52","author":"Vigneron","year":"2014","journal-title":"Discrete Comput. Geom."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1963190.2019578","article-title":"Motorcycle graphs: Stochastic properties motivate an efficient yet simple implementation","volume":"16","author":"Huber","year":"2011","journal-title":"J. Exp. Algorithmics"},{"key":"ref_7","unstructured":"Aurenhammer, F., and Steinkogler, M. (2022, January 14\u201316). An insertion strategy for motorcycle graphs. Proceedings of the 38th European Workshop on Computational Geometry, Perugia, PG, Italy."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/jagm.1995.0797","article-title":"Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations","volume":"23","author":"Goodrich","year":"1997","journal-title":"J. Algorithms"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Pach, J. (1993). Backwards Analysis of Randomized Geometric Algorithms. New Trends in Discrete and Computational Geometrys, Springer.","DOI":"10.1007\/978-3-642-58043-7"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"105984","DOI":"10.1016\/j.dib.2020.105984","article-title":"Salzburg Database of Polygonal Data: Polygons and Their Generators","volume":"31","author":"Eder","year":"2020","journal-title":"Data Brief"},{"key":"ref_11","unstructured":"Natural Earth (2022, May 06). Free Vector and Raster Map Data. Available online: https:\/\/www.naturalearthdata.com\/."},{"key":"ref_12","unstructured":"DIVA-GIS (2022, May 06). Free Spatial Data. Available online: https:\/\/www.diva-gis.org\/Data."},{"key":"ref_13","unstructured":"Ladurner, C. (2022). On the Incremental Construction of Motorcycle Graphs. [Master\u2019s Thesis, Graz University of Technology]."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Golumbic, M. (1980). Algorithm Graph Theory and Perfect Graphs, Academic Press.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"ref_15","unstructured":"Cormen, T., Leiserson, C., Rivest, R., and Stein, C. (2009). Introduction to Algorithms, MIT Press. [3rd ed.]."},{"key":"ref_16","unstructured":"Aurenhammer, F., and Steinkogler, M. (2018, January 21\u201323). On merging straight skeletons. Proceedings of the 34th European Workshop on Computational Geometry, Berlin, Germany."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/225\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T23:38:59Z","timestamp":1760139539000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/15\/7\/225"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,27]]},"references-count":16,"journal-issue":{"issue":"7","published-online":{"date-parts":[[2022,7]]}},"alternative-id":["a15070225"],"URL":"https:\/\/doi.org\/10.3390\/a15070225","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2022,6,27]]}}}