Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Extracting Wikipedia Data to Enrich Spatial Information Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Finding the Intersection Points of Networks

verfasst von : Niels Neumann, Frank Phillipson

Erschienen in: Innovations for Community Services

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Two algorithms have been constructed that find the intersections between two sets of line segments in practical networks used for planning and routing, solving the implementation issues of existing algorithms. One of the algorithms is a generalisation of the Bentley-Ottmann-algorithm, relaxing the assumptions in the original algorithm, the other is a smart brute force algorithm. In this article the algorithms are elaborated and will be tested, using real data sets constructed from street networks and trench networks. Both algorithms find all the intersections but with a difference in calculation time.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Vorheriges Kapitel Markov Random Walk vs. Higher-Order Factorization Machines: A Comparison of State-of-the-Art Recommender Algorithms
Nächstes Kapitel Distributed Network Infrastructure for Community Services in the Framework of Next Generation Mobile Networks
Fußnoten
1
Intersection means intersection in the two dimensional projection.
 
2
Note that the Bentley-Ottmann-algorithm is output-sensitive, meaning that the complexity and therefore the running times depend on the size of the output.
 
Literatur
1.
Agarwal, P.K., Sharir, M.: Red-blue intersection detection algorithms, with applications to motion planning and collision detection. SIAM J. Comput. 19(2), 297–321 (1990)MathSciNetCrossRefMATH
2.
Arge, L., Mølhave, T., Zeh, N.: Cache-oblivious red-blue line segment intersection. In: Halperin, D., Mehlhorn, K. (eds.) ESA 2008. LNCS, vol. 5193, pp. 88–99. Springer, Heidelberg (2008). doi:10.​1007/​978-3-540-87744-8_​8 CrossRef
3.
Balaban, I.: An optimal algorithm for finding segments intersections. In: Proceedings of the Eleventh Annual Symposium on Computational Geometry, SCG 1995, pp. 211–219. ACM, New York (1995)
4.
Bentley, J., Ottmann, T.: Algorithms for reporting and counting geometric intersections. IEEE Trans. Comput. 28(9), 643–647 (1979)CrossRefMATH
5.
Chazelle, B., Edelsbrunner, H.: An optimal algorithm for intersecting line segments in the plane. J. ACM 39(1), 1–54 (1992)MathSciNetCrossRefMATH
6.
Clarkson, K., Shor, P.: Applications of random sampling in computational geometry, II. Discret. Comput. Geom. 4(5), 387–421 (1989)MathSciNetCrossRefMATH
7.
Mantler, A., Snoeyink, J.: Intersecting red and blue line segments in optimal time and precision. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 2000. LNCS, vol. 2098, pp. 244–251. Springer, Heidelberg (2001). doi:10.​1007/​3-540-47738-1_​23 CrossRef
8.
Mes, M.R., Iacob, M.E.: Synchromodal transport planning at a logistics service provider. In: Zijm, H., Klumpp, M., Clausen, U., ten Hompel, M. (eds.) Logistics and Supply Chain Innovation, pp. 23–36. Springer, Heidelberg (2016)CrossRef
9.
10.
Mulmuley, K.: A fast planar partition algorithm. I. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 580–589 (1988)
11.
Phillipson, F.: Efficient algorithms for infrastructure networks: planning issues and economic impact. Ph.D. thesis, VU Amsterdam (2014)
12.
Sedgewick, R., Wayne, K.: Algorithms, 4th edn. Addison-Wesley, Boston (2011)
13.
Shamos, M., Hoey, D.: Geometric intersection problems. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, pp. 208–215 (1976)
14.
SteadieSeifi, M., Dellaert, N.P., Nuijten, W., Van Woensel, T., Raoufi, R.: Multimodal freight transportation planning: a literature review. Eur. J. Oper. Res. 233(1), 1–15 (2014)CrossRefMATH
Metadaten
Titel
Finding the Intersection Points of Networks
verfasst von
Niels Neumann
Frank Phillipson
Copyright-Jahr
2017
Buch
Innovations for Community Services

Print ISBN: 978-3-319-60446-6

Electronic ISBN: 978-3-319-60447-3

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-60447-3_8