The limited blessing of low dimensionality

DOI10.1145/2582112.2582124zbMath1395.68309arXiv1612.01171OpenAlexW2022459721MaRDI QIDQ4635529

Dániel Marx, Anastasios Sidiropoulos

Publication date: 23 April 2018

Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1612.01171

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (12)

Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams ⋮ The parameterized hardness of the \(k\)-center problem in transportation networks ⋮ The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds ⋮ An ETH-Tight Exact Algorithm for Euclidean TSP ⋮ A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs ⋮ A tight lower bound for edge-disjoint paths on planar DAGs ⋮ Fractal dimension and lower bounds for geometric problems ⋮ On Geometric Set Cover for Orthants ⋮ Unnamed Item ⋮ A Framework for Exponential-Time-Hypothesis--Tight Algorithms and Lower Bounds in Geometric Intersection Graphs ⋮ Subexponential parameterized algorithms for graphs of polynomial growth ⋮ The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: The limited blessing of low dimensionality