The limited blessing of low dimensionality: when 1-1/d is the best possible exponent for d-dimensional geometric problems (extended abstract)

DOI10.1145/2582112.2582124zbMATH Open1395.68309arXiv1612.01171OpenAlexW2022459721MaRDI QIDQ4635529FDOQ4635529

Authors: 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)

Abstract: We are studying $d$-dimensional geometric problems that have algorithms with $1-1/d$ appearing in the exponent of the running time, for example, in the form of $2^{n^{1-1/d}}$ or $n^{k^{1-1/d}}$. This means that these algorithms perform somewhat better in low dimensions, but the running time is almost the same r all large values $d$ of the dimension. Our main result is showing that for some of these problems the dependence on $1-1/d$ is best possible under a standard complexity assumption. We show that, assuming the Exponential Time Hypothesis, --- $d$-dimensional Euclidean TSP on $n$ points cannot be solved in time $2^{O(n^{1-1/d-epsilon})}$ for any $epsilon>0$, and --- the problem of finding a set of $k$ pairwise nonintersecting $d$-dimensional unit balls/axis parallel unit cubes cannot be solved in time $f(k)n^{o(k^{1-1/d})}$ for any computable function $f$. These lower bounds essentially match the known algorithms for these problems. To obtain these results, we first prove lower bounds on the complexity of Constraint Satisfaction Problems (CSPs) whose constraint graphs are $d$-dimensional grids. We state the complexity results on CSPs in a way to make them convenient starting points for problem-specific reductions to particular $d$-dimensional geometric problems and to be reusable in the future for further results of similar flavor.

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

Recommendations

• Fractal dimension and lower bounds for geometric problems
• scientific article; zbMATH DE number 7236474
• The Complexity of Geometric Problems in High Dimension
• Geometric clustering, fixed-parameter tractability and lower bounds with respect to the dimension
• The parameterized complexity of some geometric problems in unbounded dimension

Mathematics Subject Classification ID

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

Cited In (11)

• A Tight Lower Bound for Edge-Disjoint Paths on Planar DAGs
• Subexponential parameterized algorithms for graphs of polynomial growth
• A tight lower bound for edge-disjoint paths on planar DAGs
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• Fractal dimension and lower bounds for geometric problems
• On Geometric Set Cover for Orthants
• The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds
• An ETH-Tight Exact Algorithm for Euclidean TSP
• Title not available (Why is that?)
• The parameterized hardness of the \(k\)-center problem in transportation networks
• The fine-grained complexity of multi-dimensional ordering properties

This page was built for publication: The limited blessing of low dimensionality: when \(1-1/d\) is the best possible exponent for \(d\)-dimensional geometric problems (extended abstract)

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