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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Hybrid Example-Based Single Image Super-Resolution Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Computing Voronoi Diagrams of Line Segments in ℝ K in O(n log n) Time

verfasst von : Jeffrey W. Holcomb, Jorge A. Cobb

Erschienen in: Advances in Visual Computing

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The theoretical bounds on the time required to compute a Voronoi diagram of line segments in 3D are the lower bound of Ω(n 2) and the upper bound of O(n 3+ε). We present a method here for computing Voronoi diagrams of line segments in O(2a k n log 2n + 2b k n log 2n + 14n + 12c 1 n) for k-dimensional space. We also present a modification to the Bowyer-Watson method to bring its runtime down to a tight O(n log n).

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 Region Growing Selection Technique for Dense Volume Visualization
Nächstes Kapitel Visualizing Aldo Giorgini’s Ideal Flow
Literatur
1.
Delahaye, D., Puechmorel, S.: 3D airspace sectoring by evolutionary computation. In: Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation, pp. 1637–1644 (2006)
2.
Cheddad, A., Mohamad, D., Manaf, A.: Exploiting voronoi diagram properties in face segmentation and feature extraction. Pattern Recogn. 41, 3842–3859 (2008)MATHCrossRef
3.
Sabha, M., Dutré, P.: Feature-based texture synthesis and editing using voronoi diagrams. In: Sixth International Symposium on Voronoi Diagrams, pp. 165–170 (2009)
4.
Agarwal, P.D., Shwarzkopf, O., Harir, M.: The Overlay of Lower Envelopes and its Applications. Disc. Comput. Geom. 15, 1–13 (1996)MATHCrossRef
5.
6.
Descartes, R.: Principia Philosophiǣ, Amsterdam (1644)
7.
Dirichelt, P.: Über die Reduction der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen. Journal Für Die Reine Und Angewandte Mathematik, Berlin 40, 209–227 (1850)CrossRef
8.
Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiqes, Premier Mémoire, Sur quelques propriétés des formes quadratiques positives parafites. Journal Für die reine und angewandte, Mathematik, Berlin 133, 97–102 (1908)MATHMathSciNet
9.
Voronoi, G.: Nouvelles applications des paramètres continus à la théorie des formes quadratiqes, Deuxième Mémoire, Recherches sur les parallélloèdres primitifs. Journal Für die reine und angewandte, Mathematik, Berlin 134, 198–287 (1908)MATHMathSciNet
10.
Voronoi, G.: Nouvelles applications des paramètres continus à théorie des formes quadratiqes, Deuxième Mémoire, Recherches sur les parallélloèdres primitifs. Journal Für die reine und angewandte, Mathematik, Berlin 136, 67–182 (1909)MATHMathSciNet
11.
Watson, D.F.: Computing the n-dimensional delaunay tessellation with application to voronoi polytopes. Comput. J. 24(2), 167–172 (1981)CrossRefMathSciNet
12.
13.
Boada, I., Coll, N., Madern, N., Sellarès, J.: Approximations of 2D and 3D Generalized Voronoi Diagrams. International Journal of Computer Mathematics 85(7), 1003–1022 (2008)MATHCrossRefMathSciNet
14.
Held, M.: VRONI: an engineering approach to the reliable and efficient computation of voronoi diagrams of points and line segments. Comput. Geom. 18(2), 95–123 (2001)MATHCrossRefMathSciNet
15.
Held, M., Huber, S.: Topology-oriented incremental computation of voronoi diagrams of circular arcs and straight-line segments. Comput. Aided Des. 41, 327–338 (2009)MATHCrossRef
16.
Gold, C., Remmele, P., and Roos, T.: Voronoi diagrams of line segments made easy. In: Canadian Conference on Computational Geometry (1995)
17.
Hemmer, M., Setter, O., Halperin, D.: Constructing the exact voronoi diagram of arbitrary lines in three-dimensional space with fast point-location. In: 18th Annual European Symposium, pp. 6–8 (2010)
18.
Holcomb, J.W., Cobb, J.A.: Voronoi diagrams of line segments in 3D, with application to automatic rigging. In: Bebis, G., Boyle, R., Parvin, B., Koracin, D., McMahan, R., Jerald, J., Zhang, H., Drucker, S.M., Kambhamettu, C., El Choubassi, M., Deng, Z., Carlson, M. (eds.) ISVC 2014, Part I. LNCS, vol. 8887, pp. 75–86. Springer, Heidelberg (2014)
19.
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. The MIT Press, Cambridge (2001)MATH
20.
Kepler, J.: Strena seu de Nive Sexangula, 1611
21.
Metadaten
Titel
Computing Voronoi Diagrams of Line Segments in ℝ K in O(n log n) Time
verfasst von
Jeffrey W. Holcomb
Jorge A. Cobb
Copyright-Jahr
2015
Buch
Advances in Visual Computing

Print ISBN: 978-3-319-27862-9

Electronic ISBN: 978-3-319-27863-6

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-27863-6_71

Premium Partner

    Bildnachweise