Voronoi diagrams with barriers and the shortest diagonal problem

DOI10.1016/0020-0190(89)90043-4zbMath0677.68047OpenAlexW2009835586MaRDI QIDQ1123618

Andrzej Lingas

Publication date: 1989

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

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90043-4

zbMATH Keywords

Voronoi diagramplanar straight-line graphshortest diagonal problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Convex sets in (2) dimensions (including convex curves) (52A10) Graph theory (05C99)

Related Items

Finding constrained and weighted Voronoi diagrams in the plane ⋮ Fast skeleton construction ⋮ Algorithms for computing best coverage path in the presence of obstacles in a sensor field ⋮ Finding a shortest diagonal of a simple polygon in linear time ⋮ Fast algorithms for greedy triangulation ⋮ Efficiently updating constrained Delaunay triangulations ⋮ Fast algorithms for greedy triangulation ⋮ On the complexity of two circle connecting problems

Cites Work

• Generalized Delaunay triangulation for planar graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item