A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM

DOI10.1142/S0218195909002952MaRDI QIDQ5322316zbMATH OpenOpenAlexFDO

Authors Marc Benkert, Joachim Gudmundsson, Christian Knauer, René van Oostrum, Alexander Wolff

Publication date 20 July 2009

Published in International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0218195909002952

zbMATH Keywords

APX-hardgeometric packing

Mathematics Subject Classification ID

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

Recommendations

• A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem
• Approximation of geometric dispersion problems
• Packing two disks into a polygonal environment.
• scientific article; zbMATH DE number 1182762
• scientific article; zbMATH DE number 1796962

Cites work

• A study on two geometric location problems
• An optimal algorithm for constructing the weighted Voronoi diagram in the plane
• Approximation of geometric dispersion problems
• Approximation schemes for covering and packing problems in image processing and VLSI
• Heuristic and Special Case Algorithms for Dispersion Problems
• Improved algorithms for discs and balls using power diagrams
• Optimal packing and covering in the plane are NP-complete
• Randomized incremental construction of abstract Voronoi diagrams

Cited in

(15)

• Dispersing points on intervals
• Repulsion-based p-dispersion with distance constraints in non-convex polygons
• Systems of distant representatives in Euclidean space
• A Polynomial-Time Approximation Algorithm for a Geometric Dispersion Problem
• scientific article; zbMATH DE number 512838 (Why is no real title available?)
• scientific article; zbMATH DE number 1182762 (Why is no real title available?)
• Placing your coins on a shelf
• Efficient approximations for the online dispersion problem
• scientific article; zbMATH DE number 824099 (Why is no real title available?)
• Intractability of assembly sequencing: unit disks in the plane
• Placing your coins on a shelf
• Approximation of geometric dispersion problems
• The dispersive art gallery problem
• (Re)packing equal disks into rectangle
• Dispersion in disks

This page was built for publication: A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR A GEOMETRIC DISPERSION PROBLEM

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