Computational complexity for the problem of optimal intersection of straight line segments by disks

DOI10.1134/S0081543818090158zbMath1414.05093OpenAlexW2922045726MaRDI QIDQ2424188

K. S. Kobylkin

Publication date: 24 June 2019

Published in: Proceedings of the Steklov Institute of Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s0081543818090158

zbMATH Keywords

computational complexityDelaunay triangulationshitting set problemcontinuous disk cover problem

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Unnamed Item
• Exact algorithms and APX-hardness results for geometric packing and covering problems
• Optimal algorithms for some intersection radius problems
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• Probabilistic bounds on the length of a longest edge in Delaunay graphs of random points in \(d\)-dimensions
• Competitive Online Routing on Delaunay Triangulations
• Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
• Algorithms – ESA 2005
• Routing with guaranteed delivery in ad hoc wireless networks