Using geometry to solve the transportation problem in the plane

DOI10.1007/BF01190848MaRDI QIDQ1894300zbMATH OpenOpenAlexFDO

Authors Pravin M. Vaidya, David Atkinson

Publication date 9 August 1995

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01190848

zbMATH Keywords

transportation problemVoronoi diagramsscaling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Faster algorithms for the geometric transportation problem
• Algorithms for the transportation problem in geometric settings
• scientific article; zbMATH DE number 742962
• Efficient Algorithms for the Hitchcock Transportation Problem
• Preconditioning for the Geometric Transportation Problem

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• A sweepline algorithm for Voronoi diagrams
• Faster Scaling Algorithms for Network Problems
• Geometry Helps in Matching
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Location of a Point in a Planar Subdivision and Its Applications
• On the construction of abstract Voronoi diagrams
• Optimal Point Location in a Monotone Subdivision
• Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems

Cited in

(5)

• Faster algorithms for the geometric transportation problem
• Algorithms for the transportation problem in geometric settings
• Preconditioning for the geometric transportation problem
• Matching point sets with respect to the earth mover's distance
• Reprint of: Optimally solving a transportation problem using Voronoi diagrams

This page was built for publication: Using geometry to solve the transportation problem in the plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1894300)