Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications

DOI10.1137/1.9781611974782.165zbMath1410.68370OpenAlexW4244317572MaRDI QIDQ4575914

Haim Kaplan, Wolfgang Mulzer, Paul Seiferth, Liam Roditty, Micha Sharir

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611974782.165

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (24)

Minimum cuts in geometric intersection graphs ⋮ Reverse shortest path problem for unit-disk graphs ⋮ Reverse shortest path problem in weighted unit-disk graphs ⋮ Geometric planar networks on bichromatic collinear points ⋮ Spanners for Directed Transmission Graphs ⋮ An optimal algorithm for \(L_1\) shortest paths in unit-disk graphs ⋮ Incremental Voronoi diagrams ⋮ Unnamed Item ⋮ Dynamic planar Voronoi diagrams for general distance functions and their algorithmic applications ⋮ Near-optimal algorithms for shortest paths in weighted unit-disk graphs ⋮ Dynamic geometric data structures via shallow cuttings ⋮ Reachability problems for transmission graphs ⋮ Spanning trees in multipartite geometric graphs ⋮ Reachability problems for transmission graphs ⋮ On the structure of higher order Voronoi cells ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Resolving SINR Queries in a Dynamic Setting ⋮ Near-Optimal Algorithms for Shortest Paths in Weighted Unit-Disk Graphs. ⋮ Two approaches to building time-windowed geometric data structures

This page was built for publication: Dynamic Planar Voronoi Diagrams for General Distance Functions and their Algorithmic Applications