Computing the map of geometric minimal cuts

DOI10.1007/s00453-012-9704-9zbMath1303.05202OpenAlexW2059004575MaRDI QIDQ476438

Evanthia Papadopoulou, Lei Xu, Jinhui Xu

Publication date: 2 December 2014

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-012-9704-9

zbMATH Keywords

computational geometryplane sweep algorithmgeometric minimal cutHausdorff Voronoi diagramoutput sensitive algorithm

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items

The L∞ Hausdorff Voronoi Diagram Revisited ⋮ On Clustering Induced Voronoi Diagrams ⋮ Influence-based Voronoi diagrams of clusters

Cites Work

• Unnamed Item
• Randomized incremental construction of abstract Voronoi diagrams
• Abstract Voronoi diagrams revisited
• Dynamic fractional cascading
• The upper envelope of piecewise linear functions: Algorithms and applications
• A sweepline algorithm for Voronoi diagrams
• Making data structures persistent
• Concrete and abstract Voronoi diagrams
• A combinatorial property of convex sets
• The Hausdorff Voronoi diagram of point clusters in the plane
• ``The big sweep: On the power of the wavefront approach to Voronoi diagrams
• Near-optimal fully-dynamic graph connectivity
• Data Structures for On-Line Updating of Minimum Spanning Trees, with Applications
• Sampling to provide or to bound: With applications to fully dynamic graph algorithms
• Sparsification—a technique for speeding up dynamic graph algorithms
• THE L_∞ VORONOI DIAGRAM OF SEGMENTS AND VLSI APPLICATIONS
• Higher Order Voronoi Diagrams of Segments for VLSI Critical Area Extraction
• Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity
• THE HAUSDORFF VORONOI DIAGRAM OF POLYGONAL OBJECTS: A DIVIDE AND CONQUER APPROACH