Farthest line segment Voronoi diagrams

DOI10.1016/j.ipl.2006.07.008zbMath1185.68769OpenAlexW2042426695MaRDI QIDQ845871

Robert L. Scot Drysdale, Franz Aurenhammer, Hannes Krasser

Publication date: 29 January 2010

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2006.07.008

zbMATH Keywords

Voronoi diagramoptimal algorithmcomputational geometryfarthest line segment

Mathematics Subject Classification ID

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

Related Items (16)

Rearranging a sequence of points onto a line ⋮ An \(O(n\log n)\) algorithm for the all-farthest-segments problem for a planar set of points ⋮ Approximation Algorithms for Finding a Minimum Perimeter Polygon Intersecting a Set of Line Segments ⋮ ON THE FARTHEST LINE-SEGMENT VORONOI DIAGRAM ⋮ Improved algorithms for the farthest colored Voronoi diagram of segments ⋮ On the central path problem ⋮ All-maximum and all-minimum problems under some measures ⋮ Discrete and mixed two-center problems for line segments ⋮ Farthest-polygon Voronoi diagrams ⋮ Voronoi Diagram for Convex Polygonal Sites with Convex Polygon-Offset Distance Function ⋮ Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction ⋮ Dispersing and grouping points on planar segments ⋮ Stabbing circles for sets of segments in the plane ⋮ Farthest segments and extremal triangles spanned by points in \(\mathbb R^3\) ⋮ Convex-straight-skeleton Voronoi diagrams for segments and convex polygons ⋮ The higher-order Voronoi diagram of line segments

Cites Work

• Unnamed Item
• Unnamed Item
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• On the all-farthest-segments problem for a planar set of points
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• Stabbing line segments
• 2-point site Voronoi diagrams
• An \(O(n\log n)\) algorithm for the all-farthest-segments problem for a planar set of points
• Proximity problems on line segments spanned by points
• Voronoui Diagrams in $L_1 (L_\infty )$ Metrics with 2-Dimensional Storage Applications
• Generalization of Voronoi Diagrams in the Plane

This page was built for publication: Farthest line segment Voronoi diagrams