The higher-order Voronoi diagram of line segments

DOI10.1007/s00453-014-9950-0zbMath1336.68265arXiv1405.3806OpenAlexW2004336806MaRDI QIDQ261375

Maksym Zavershynskyi, Evanthia Papadopoulou

Publication date: 23 March 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.3806

zbMATH Keywords

Voronoi diagramcomputational geometryline segments\(k\) nearest neighbors\(L_p\) metricorder-\(k\) Voronoi diagramplanar straight line graph

Mathematics Subject Classification ID

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

Related Items

A randomized divide and conquer algorithm for higher-order abstract Voronoi diagrams, An efficient randomized algorithm for higher-order abstract Voronoi diagrams, The Earth is nearly flat: Precise and approximate algorithms for detecting vulnerable regions of networks in the plane and on the sphere, Convex-straight-skeleton Voronoi diagrams for segments and convex polygons, Deletion in Abstract Voronoi Diagrams in Expected Linear Time.

Cites Work

• Unnamed Item
• Unnamed Item
• Farthest-polygon Voronoi diagrams
• Order-k Voronoi diagrams of sites with additive weights in the plane
• Abstract Voronoi diagrams revisited
• Farthest line segment Voronoi diagrams
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• Stabbing line segments
• The nature and meaning of perturbations in geometric computing
• New applications of random sampling in computational geometry
• Applications of random sampling in computational geometry. II
• The \(k\)-nearest-neighbor Voronoi diagram revisited
• Voronoi Diagrams and Delaunay Triangulations
• ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM
• A Randomized Divide and Conquer Algorithm for Higher-Order Abstract Voronoi Diagrams
• A SIMPLE ON-LINE RANDOMIZED INCREMENTAL ALGORITHM FOR COMPUTING HIGHER ORDER VORONOI DIAGRAMS
• 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
• FURTHEST SITE ABSTRACT VORONOI DIAGRAMS
• The Clarkson–Shor Technique Revisited and Extended
• On Higher Order Voronoi Diagrams of Line Segments
• On the Complexity of Higher Order Abstract Voronoi Diagrams