Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Delta-Diagram Based Synthesis for Cross Layer Optimization Modeling of IoT Read chapter Read first chapter

2018 | OriginalPaper | Chapter

Neighbourhood Graphs and Locally Minimal Triangulations

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

Published in: Transactions on Computational Science XXXIII

Publisher: Springer Berlin Heidelberg

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter A Distance Matrix Completion Approach to 1-Round Algorithms for Point Placement in the Plane
Literature
1.
2.
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.
20.
Metadata
Title
Neighbourhood Graphs and Locally Minimal Triangulations
Authors
Ivana Kolingerová
Tomáš Vomáčka
Martin Maňák
Andrej Ferko
Copyright Year
2018
Publisher
Springer Berlin Heidelberg
Book
Transactions on Computational Science XXXIII

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

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

Copyright Year: 2018

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

Premium Partner

    Image Credits