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:
An Optimal Algorithm for Tiling the Plane with a Translated Polyomino Read chapter Read first chapter

2015 | OriginalPaper | Chapter

Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures

Authors : Elena Khramtcova, Evanthia Papadopoulou

Published in: Algorithms and Computation

Publisher: Springer Berlin Heidelberg

Log in

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

search-config
loading …

Abstract

We present linear-time algorithms to construct tree-like Voronoi diagrams with disconnected regions after the sequence of their faces along an enclosing boundary (or at infinity) is known. We focus on the farthest-segment Voronoi diagram, however, our techniques are also applicable to constructing the order-\((k{+}1)\) subdivision within an order-k Voronoi region of segments and updating a nearest-neighbor Voronoi diagram of segments after deletion of one site. Although tree-structured, these diagrams illustrate properties surprisingly different from their counterparts for points. The sequence of their faces along the relevant boundary forms a Davenport-Schinzel sequence of order \(\ge 2\). Once this sequence is known, we show how to compute the corresponding Voronoi diagram in linear time, expected or deterministic, augmenting the existing linear-time frameworks for points in convex position with the ability to handle non-point sites and multiple Voronoi faces.

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 Model-Based Classification of Trajectories
next chapter Unfolding Orthogonal Polyhedra with Linear Refinement
Footnotes
1
Order-3 for the farthest-segment Voronoi diagram [2, 12], order-4 for the order-k segment Voronoi diagram (easy to derive from [13]), order-2 for disjoint segments or the corresponding abstract Voronoi diagrams [10, 13].
 
Literature
1.
Aggarwal, A., Guibas, L., Saxe, J., Shor, P.: A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom. 4, 591–604 (1989)MathSciNetCrossRefMATH
2.
3.
Aurenhammer, F., Klein, R., Lee, D.T.: Voronoi Diagrams and Delaunay Triangulations. World Scientific, Singapore (2013)CrossRefMATH
4.
Bohler, C., Cheilaris, P., Klein, R., Liu, C.-H., Papadopoulou, E., Zavershynskyi, M.: On the complexity of higher order abstract Voronoi diagrams. In: Kwiatkowska, M., Peleg, D., Fomin, F.V., Freivalds, R.U. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 208–219. Springer, Heidelberg (2013) CrossRef
5.
Bohler, C., Klein, R., Liu, C.: Forest-like abstract Voronoi diagrams in linear time. In: Proceedings of the 26th CCCG (2014)
6.
Cheong, O., Everett, H., Glisse, M., Gudmundsson, J., Hornus, S., Lazard, S., Lee, M., Na, H.: Farthest-polygon Voronoi diagrams. Comput. Geom. 44(4), 234–247 (2011)MathSciNetCrossRefMATH
7.
Chew, L.P.: Building Voronoi diagrams for convex polygons in linear expected time. Technical report, Dartmouth College, Hanover, USA (1990)
8.
Chin, F., Snoeyink, J., Wang, C.A.: Finding the medial axis of a simple polygon in linear time. Discrete Comput. Geom. 21(3), 405–420 (1999)MathSciNetCrossRefMATH
9.
Klein, R., Lingas, A.: Hamiltonian abstract Voronoi diagrams in linear time. In: Du, D.-Z., Zhang, X.-S. (eds.) ISAAC 1994. LNCS, vol. 834, pp. 11–19. Springer, Heidelberg (1994) CrossRef
10.
11.
Papadopoulou, E.: Net-aware critical area extraction for opens in VLSI circuits via higher-order Voronoi diagrams. IEEE T. Comput. Aid. D. 30(5), 704–716 (2011)CrossRef
12.
13.
Metadata
Title
Linear-Time Algorithms for the Farthest-Segment Voronoi Diagram and Related Tree Structures
Authors
Elena Khramtcova
Evanthia Papadopoulou
Copyright Year
2015
Publisher
Springer Berlin Heidelberg
Book
Algorithms and Computation

Print ISBN: 978-3-662-48970-3

Electronic ISBN: 978-3-662-48971-0

Copyright Year: 2015

DOI
https://doi.org/10.1007/978-3-662-48971-0_35

Premium Partner

    Image Credits