An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs

DOI10.1016/0020-0190(90)90054-2zbMath0703.68059OpenAlexW2014645446MaRDI QIDQ916391

Chuan Yi Tang, Nen-Fu Huang, Maw-Shang Chang

Publication date: 1990

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(90)90054-2

zbMATH Keywords

computational geometrygeographic neighborhood graphthe oriented Voronoi diagram

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (9)

Approximating geometric bottleneck shortest paths ⋮ Voronoi-like partition of lattice in cellular automata ⋮ Steiner minimal trees in \(L^ 2_ p\) ⋮ Spanners for Directed Transmission Graphs ⋮ Minimum weight Euclidean \((1+\varepsilon)\)-spanners ⋮ Unnamed Item ⋮ On the restricted 1-Steiner tree problem ⋮ On the restricted \(k\)-Steiner tree problem ⋮ Closest-pair queries in fat rectangles

Cites Work

• Unnamed Item
• Computing relative neighbourhood graphs in the plane
• A sweepline algorithm for Voronoi diagrams
• The 1-steiner tree problem

This page was built for publication: An optimal algorithm for constructing oriented Voronoi diagrams and geograph neighborhood graphs