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:
A Delta-Diagram Based Synthesis for Cross Layer Optimization Modeling of IoT Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Neighbourhood Graphs and Locally Minimal Triangulations

verfasst von : Ivana Kolingerová, Tomáš Vomáčka, Martin Maňák, Andrej Ferko

Erschienen in: Transactions on Computational Science XXXIII

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config
loading …

Abstract

Neighbourhood (or proximity) graphs, such as nearest neighbour graph, closest pairs, relative neighbourhood graph and k-nearest neighbour graph are useful tools in many tasks inspecting mutual relations, similarity and closeness of objects. Some of neighbourhood graphs are subsets of Delaunay triangulation (DT) and this relation can be used for efficient computation of these graphs. This paper concentrates on relation of neighbourhood graphs to the locally minimal triangulation (LMT) and shows that, although generally these graphs are not LMT subgraphs, in most cases LMT contains all or many edges of these graphs. This fact can also be used for the neighbourhood graphs computation, namely in kinetic problems, because LMT computation is easier.

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 A Distance Matrix Completion Approach to 1-Round Algorithms for Point Placement in the Plane
Literatur
1.
2.
Basch, J., Guibas, L.J., Hershberger, J.: Data structures for mobile data. J. Algorithms 31(1), 1–28 (1999)MathSciNetCrossRef
3.
4.
Beirouti, R., Snoeyink, J.: Implementations of the LMT heuristic for minimum weight triangulation. In: Proceedings of the Fourteenth Annual Symposium on Computational Geometry, SCG 1998, pp. 96–105. ACM, New York (1998)
5.
Bose, P., Devroye, L., Evans, W.: Diamonds are not a minimum weight triangulation’s best friend. Int. J. Comput. Geom. Appl. 12(06), 445–453 (2002)MathSciNetCrossRef
6.
Cho, H.G.: On the expected number of common edges in Delaunay and greedy triangulation. J. WSCG 5(1–3), 50–59 (1997)
7.
Dey, T.K.: Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics). Cambridge University Press, New York (2006)
8.
Dickerson, M.T., Keil, J.M., Montague, M.H.: A large subgraph of the minimum weight triangulation. Discrete Comput. Geom. 18(3), 289–304 (1997)MathSciNetCrossRef
9.
Dickerson, M.T., Montague, M.H.: A (usually?) connected subgraph of the minimum weight triangulation. In: Proceedings of the Twelfth Annual Symposium on Computational Geometry, SCG 1996, pp. 204–213. ACM, New York (1996)
10.
Gavrilova, M., Rokne, J.: Swap conditions for dynamic Voronoi diagrams for circles and line segments. Comput. Aided Geom. Des. 16(2), 89–106 (1999)MathSciNetCrossRef
11.
Gavrilova, M., Rokne, J.: Updating the topology of the dynamic Voronoi diagram for spheres in Euclidean d-dimensional space. Comput. Aided Geom. Des. 20(4), 231–242 (2003)MathSciNetCrossRef
12.
Guibas, L., Russel, D.: An empirical comparison of techniques for updating Delaunay triangulations. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry, SCG 2004, pp. 170–179. ACM, New York (2004)
13.
Kim, Y.S., Park, D.G., Jung, H.Y., Cho, H.G., Dong, J.J., Ku, K.J.: An improved TIN compression using Delaunay triangulation. In: Proceedings of Seventh Pacific Conference on Computer Graphics and Applications (Cat. No.PR00293), pp. 118–125 (1999)
14.
Maus, A., Drange, J.M.: All closest neighbors are proper delaunay edges generalized, and its application to parallel algorithms. In: Proceedings of Norwegian informatikkonferanse, pp. 1–12 (2010)
15.
Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial tessellations: concepts and applications of Voronoi diagrams. Probability and Statistics, 2nd edn. Wiley, NYC (2000)
16.
17.
Spelič, D., Novak, F., Žalik, B.: Delaunay triangulation benchmarks. J. Electr. Eng. 59(1), 49–52 (2008)
18.
Su, P., Drysdale, R.L.S.: A comparison of sequential Delaunay triangulation algorithms. Comput. Geom. 7(5), 361–385 (1997)MathSciNetCrossRef
19.
Toussaint, G.T.: The relative neighbourhood graph of a finite planar set. Pattern Recogn. 12(4), 261–268 (1980)MathSciNetCrossRef
20.
Metadaten
Titel
Neighbourhood Graphs and Locally Minimal Triangulations
verfasst von
Ivana Kolingerová
Tomáš Vomáčka
Martin Maňák
Andrej Ferko
Copyright-Jahr
2018
Verlag
Springer Berlin Heidelberg
Buch
Transactions on Computational Science XXXIII

Print ISBN: 978-3-662-58038-7

Electronic ISBN: 978-3-662-58039-4

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-662-58039-4_7