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.2582124MaRDI QIDQ4635529zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(11)

• The fine-grained complexity of multi-dimensional ordering properties
• The parameterized hardness of the \(k\)-center problem in transportation networks
• An ETH-Tight Exact Algorithm for Euclidean TSP
• Fractal dimension and lower bounds for geometric problems
• scientific article; zbMATH DE number 7236474 (Why is no real title available?)
• A framework for exponential-time-hypothesis-tight algorithms and lower bounds in geometric intersection graphs
• On Geometric Set Cover for Orthants
• The homogeneous broadcast problem in narrow and wide strips. II: Lower bounds
• 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

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)