The \(k\)-nearest-neighbor Voronoi diagram revisited

DOI10.1007/s00453-013-9809-9zbMath1315.68255MaRDI QIDQ2346966

Evanthia Papadopoulou, Chih-Hung Liu, Der-Tsai Lee

Publication date: 26 May 2015

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-013-9809-9

zbMATH Keywords

Voronoi diagrams; \(k\)-nearest neighbors; higher-order Voronoi diagrams; segment dragging queries

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

Related Items

Minimum-width annulus with outliers: circular, square, and rectangular cases, The higher-order Voronoi diagram of line segments, A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams, The \(\sigma\)-neighborhood skyline queries

Cites Work

• Unnamed Item
• Unnamed Item
• On levels in arrangements and Voronoi diagrams
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• The number of small semispaces of a finite set of points in the plane
• \(L_ 1\) shortest paths among polygonal obstacles in the plane
• Higher order Delaunay triangulations
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• Dynamic half-space range reporting and its applications
• A semidynamic construction of higher-order Voronoi diagrams and its randomized analysis
• An Output-Sensitive Approach for the L 1/L  ∞  k-Nearest-Neighbor Voronoi Diagram
• A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS
• ON STRUCTURAL AND GRAPH THEORETIC PROPERTIES OF HIGHER ORDER DELAUNAY GRAPHS
• Constructing Arrangements of Lines and Hyperplanes with Applications
• An Improved Algorithm for Constructing kth-Order Voronoi Diagrams
• Two-Dimensional Voronoi Diagrams in the L _p -Metric
• On k-Nearest Neighbor Voronoi Diagrams in the Plane
• Constructing Levels in Arrangements and Higher Order Voronoi Diagrams
• Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions
• THE L_∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS
• Constructing Belts in Two-Dimensional Arrangements with Applications
• On Steiner’s Problem with Rectilinear Distance
• A new duality result concerning Voronoi diagrams